#P1811. 最短路

最短路

题目描述

给定一个包含 NN 个点,MM 条边的无向图,每条边的边权均为 11

再给定 KK 个三元组 (A,B,C)(A,B,C),表示从 AA 点走到 BB 点后不能往 CC 点走。注意三元组是有序的,如可以从 BB 点走到 AA 点再走到 CC

现在你要在 KK 个三元组的限制下,找出 11 号点到 NN 号点的最短路径,并输出任意一条合法路径,会有 Check 检查你的输出。

输入格式

输入文件第一行有三个数 NNMMKK,意义如题目所述。

接下来 MM 行每行两个数 AABB,表示 AABB 间有一条边。

再下面 KK 行,每行三个数 (A,B,C)(A,B,C) 描述一个三元组。

输出格式

输出文件共两行数,第一行一个数 SS 表示最短路径长度。 。

第二行 S+1S+1 个数,表示从 11NN 所经过的节点。 。

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

提示

对于 40%40\% 的数据满足 N10N \le 10M20M \le 20K5K \le 5

对于 100%100\% 的数据满足 N3000N \le 3000M20000M \le 20000K100000K \le 100000