← 返回题目列表

Codeforces · 59/E

E. 最短路径

中文机器翻译题面 查看原题

古代贝尔兰有 n 个城市和 m 条等长的双向道路。城市用 1 到 n 之间的整数进行编号。根据一个古老的迷信,如果一个旅行者连续访问了三个城市 ai、bi、ci,而没有访问它们之间的其他城市,那么他将面临一场巨大的灾难。总共有 k 个这样的城市三元组。每个三元组都是有序的,这意味着,例如,您可以按以下顺序访问城市:ai、ci、bi。 Vasya 想要从城市 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),它们是禁止的三元组。每个有序三元组被列出多次。每个三联体中的所有三个城市都是不同的。

从城市 1 通过公路无法到达城市 n。

输出

如果没有从 1 到 n 的路径,则打印 -1。否则,在第一行打印从城市 1 到城市 n 的最短路径上的道路 d 的数量。在第二行打印 d + 1 个数字——Vasya 的任何可能的最短路径。路径应从城市 1 开始,到城市 n 结束。

示例

输入 #1

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

输出 #1

2
1 3 4

输入 #2

3 1 0
1 2

输出 #2

-1

输入 #3

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

输出 #3

4
1 3 2 3 4