In Ancient Berland there were n cities and m two-way roads of equal length. The cities are numbered with integers from 1 to n inclusively. According to an ancient superstition, if a traveller visits three cities ai, bi, ci in row, without visiting other cities between them, a great disaster awaits him. Overall there are k such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: ai, ci, bi. Vasya wants to get from the city 1 to the city n and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.

Input

The first line contains three integers n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 105) which are the number of cities, the number of roads and the number of the forbidden triplets correspondingly. 

Then follow m lines each containing two integers xi, yi (1 ≤ xi, yi ≤ n) which are the road descriptions. The road is described by the numbers of the cities it joins. No road joins a city with itself, there cannot be more than one road between a pair of cities. 

Then follow k lines each containing three integers ai, bi, ci (1 ≤ ai, bi, ci ≤ n) which are the forbidden triplets. Each ordered triplet is listed mo more than one time. All three cities in each triplet are distinct.

City n can be unreachable from city 1 by roads.

Output

If there are no path from 1 to n print -1. Otherwise on the first line print the number of roads d along the shortest path from the city 1 to the city n. On the second line print d + 1 numbers — any of the possible shortest paths for Vasya. The path should start in the city 1 and end in the city n.

Examples

Input

4 4 1
1 2
2 3
3 4
1 3
1 4 3


Output

2
1 3 4


Input

3 1 0
1 2


Output

-1


Input

4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4


Output

4
1 3 2 3 4
def solve():#Algoritmo que soluciona el ejercicio
    d[0][1]=0#Caso base para empezar el algoritmo
    q=[(0,1)]#Introducimos una arista "fantasma" para trabajar el algoritmo
    while q:#Mientras hayan elementos la cola 
        u,v = q.pop(0)#Sacamos el primer elemento que introducimos (FIFO)
        dist=d[u][v]+1#La distancia con la que se alcancen los siguientes vertices van a ser 1+la distancia con la que se llego a la arista que estamos analizando
        for i in Adj[v]:#Iteramos por cada uno de los adyacentes al vertice de destino de la arista
            if dist<d[v][i] and not (u,v,i) in trios_prohibidos:#Si la destancia con la que llegamos es menor que la que ya teniamos antes y la arista mas el vertice que teniamos no esta en los trios prohibidos
                d[v][i]=dist#Actualizamos la distancia
                pi[v][i]=u#Actualizamos el vertice desde el cual se llego a la arista
                q.append((v,i))#Agregamos la arista al final de la cola para so posterior analisis
                if i == n:#Si alcalzamos el vertice final entonces ya tendriamos la respuesta
                    print(dist)#Imprime la distancia minima
                    print_path(v,i)#Imprime el camino minimo
                    return
    print(-1)#En caso de no encontrar un camino imprime -1
def print_path(u,v):#Imprime el camino recursivamente utilizando pi[][]
    if u:
        print_path(pi[u][v],u)
    print (str(v), end=" ")

n,m,k =map(int,input().split())#Obtiene los valores de la entrada
Adj=[[] for i in range (n+1)]#Lista de adyacencia de los vertices
d=[[2*m+1]*(n+1) for i in range(n+1)]#Matriz que representa en [u][v] la cota maxima con la cual se alcanza la arista u-v. Empieza en 2*m+1 ya que en el grafo hay maximo 2m aristas
pi=[[0]*(n+1) for i in range(n+1)]#Guarda en [u][v] el vertice desde el cual se alcanza la arista u-v
for i in range(m):#Obtenemos cada uno de los m pares de vertices que representan las arista y los agregamos a sus respectivas listas de adyacencias
    x, y=map(int,input().split())
    Adj[x].append(y)
    Adj[y].append(x)
trios_prohibidos=set()#Conjunto que almacena cada uno de los trios prohibidos
for i in range(k):#Obtenemos los trios prohibidos de la entrada y los almacenamos
    trios_prohibidos.add(tuple(map(int,input().split())))
solve()#Mandamos a ejecutar el algoritmo para solucionar el ejercicio 
