E. Кратчайший путь
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В Древней Берляндии n городов и m двунаправленных дорог одинаковой длины. Города пронумерованы целыми числами от 1 до n включительно. Согласно древней примете, если путешественник посетит подряд (не заходя ни в какие другие) три города ai, bi, ci, его ждет большая беда. И всего есть k таких троек городов. Каждая тройка является упорядоченной, это означает, что, например, посещать города в порядке ai, ci, bi можно. Вася хочет попасть из города 1 в город n, не нарушая приметы. Выясните, какое наименьшее число дорог ему нужно пройти. Также требуется найти один из его возможных маршрутов.

Входные данные

В первой строке записаны три целых числа n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 105) — количество городов, количество дорог и количество запрещенных троек соответственно.

Далее следует m строк по два целых числа xi, yi (1 ≤ xi, yi ≤ n) — описания дорог. Дорога описывается номерами городов, которые она соединяет. Никакая дорога не соединяет город с самим собой, между парой городов может быть не более одной дороги.

Далее следует k строк по три целых числа ai, bi, ci (1 ≤ ai, bi, ci ≤ n) — запрещенные тройки. Каждая упорядоченная тройка перечислена не более одного раза. Все три города в каждой тройке попарно различны.

Город n может быть недостижим из города 1 по дорогам.

Выходные данные

Если пути из 1 в n не существует, выведите -1. Иначе в первой строке выведите количество дорог d в кратчайшем пути из города 1 в город n. Во второй строке выведите d + 1 чисел — любой из возможных кратчайших маршрутов Васи. Маршрут должен начинаться с города 1 и заканчиваться в городе n.

Примеры
Входные данные
4 4 1
1 2
2 3
3 4
1 3
1 4 3
Выходные данные
2
1 3 4
Входные данные
3 1 0
1 2
Выходные данные
-1
Входные данные
4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4
Выходные данные
4
1 3 2 3 4