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 *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> 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: *a*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>. 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.
The first line contains three integers *n*, *m*, *k* (2 ≤ *n* ≤ 3000, 1 ≤ *m* ≤ 20000, 0 ≤ *k* ≤ 10<sup class="upper-index">5</sup>) 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 *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ *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 *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> ≤ *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.
import sys
sys.setrecursionlimit(100000)
def solve(pos):#Algoritmo recursivo para buscar todos los caminos posibles
    if pos == n:#Caso de parada del algoritmo recursivo que nos dice cuando llegamos al final
        posibles_caminos.append(camino[:])#Guardamos una copia del camino en los posibles caminos
        return
    for i in Adj[pos][:]:#Itaramos por cada uno de los vertices adyacentes. Hacemos una copia por que lo modificaremos en el interior
        camino.append(i)#Agregamos el vertice al camino
        Adj[pos].remove(i)#Removemos la arista para no tomarla repetida
        solve(i)#LLamamos recursivamente en la siguiente posicion
        Adj[pos].append(i)#Volvemos a insertar la arista
        camino.pop(len(camino)-1)#Sacamos el vertice del final del camino
def get_result():#Metodo para eliminar los no validos y quedarnos con el menor
    minimo=0#Aqui se va almacenar la cantidad de vertices en el camino de costo minimo
    min_cam=[]#Almacena el camino de costo minimo
    for c in posibles_caminos:#Iteramos en todos los posibles caminos
        mal=False#Flag que nos dice si el camino contiene un trio prohibido o no
        for i in range(2,len(c)):#Iteramos por los vertices del camino 
            if (c[i-2],c[i-1],c[i]) in trios_prohibidos:#Verificamos si existen o no trios malditos
                mal=True#En caso de existir un trio levantamos el Flag
                break
        if not mal:#Si el camino no tiene un trio
            if len(c)<minimo or minimo==0:#Verificamos que no tengamos un camino o que sea menor que el camino que teniamos
                min_cam=c#Actualizamos los valores del minimo
                minimo=len(c)
    print(minimo-1)#Imprimimos la cantidad de aristas en el camino minimo
    p=""
    for i in min_cam:#Construimos el string del camino para imprimirlo
        p+=str(i)+" "
    print(p)

n,m,k =map(int,input().split())#Obtenemos los valores de la entrada
Adj=[[] for i in range(n+1)]#Lista que contine las listas de Adjacencias para cada vertice
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())))
posibles_caminos=[]#Lista que contendra cada uno de los posibles caminos
camino=[1]#El camino que vamos a estar analizando en cada momento del metodo recursivo. Empieza en 1 ya que es lo que nos pide el problema
solve(1)#Mandamos a ejecutar el metodo recursivo para obtener todos los posibles caminos
get_result()#Buscamos la solucion eliminando los caminos no validos y quedandonos con el menor de los restantes