CF59E Shortest Path

题目描述

在 Ancient Berland 有 $n$ 座城市和 $m$ 条长度均为 $1$ 的双向道路。城市从 $1$ 到 $n$ 编号。根据一个古老的迷信说法，如果一个旅行者连续访问了 $a_i,b_i,c_i$ 三座城市而不去拜访其他城市，来自东方的神秘力量将使他遭受巨大的灾害。一共有 $k$ 组这样的城市，每个三元组都是有序的，这意味着你可以按照 $a_i,c_i,b_i$ 这样的方式来访问一组城市而不遭受灾害。Vasya 想要从城市 $1$ 走到城市 $n$ 并且不受到诅咒。请告诉他最短路的长度，并输出一条路线。

输入格式

第 $1$ 行 $3$ 个整数 $n,m,k(2\le n\le 3000,1\le m\le2\times10^4,0\le k\le10^5)$，分别表示城市数、路径数以及三元组数量。

接下来 $m$ 行，每行 $2$ 个整数 $x_i,y_i(1\le x_i,y_i\le n)$，表示存在一条连接 $x_i$ 与 $y_i$ 的路，保证无重边和自环。

接下来 $k$ 行，每行 $3$ 个整数 $a_i,b_i,c_i(1\le a_i,b_i,c_i\le n)$，表示一个诅咒三元组。不存在两个相同的三元组，且三个城市两两不同。

输出格式

可能从 $1$ 号城市出发无法到达 $n$ 号城市，这种情况下输出 -1 。

否则第 $1$ 行输出最短路长度 $d$，第 $2$ 行输出 $d+1$ 个数，表示一条可行最短路径。路径必须从 $1$ 开始，在 $n$ 结束。

输入输出样例 #1

输入 #1

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

输出 #1

2
1 3 4

输入输出样例 #2

输入 #2

3 1 0
1 2

输出 #2

-1

输入输出样例 #3

输入 #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