В Древней Берляндии n городов и m двунаправленных дорог одинаковой длины. Города пронумерованы целыми числами от 1 до n включительно. Согласно древней примете, если путешественник посетит подряд (не заходя ни в какие другие) три города ai, bi, ci, его ждет большая беда. И всего есть k таких троек городов. Каждая тройка является упорядоченной, это означает, что, например, посещать города в порядке ai, ci, bi можно. Вася хочет попасть из города 1 в город n, не нарушая приметы. Выясните, какое наименьшее число дорог ему нужно пройти. Также требуется найти один из его возможных маршрутов.
Выходные данные
Если пути из 1 в n не существует, выведите -1. Иначе в первой строке выведите количество дорог d в кратчайшем пути из города 1 в город n. Во второй строке выведите d + 1 чисел — любой из возможных кратчайших маршрутов Васи. Маршрут должен начинаться с города 1 и заканчиваться в городе n.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 1
1 2
2 3
3 4
1 3
1 4 3
|
2
1 3 4
|
|
2
|
3 1 0
1 2
|
-1
|
|
3
|
4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4
|
4
1 3 2 3 4
|