最短路_NOI导刊2011提高(01)

题目描述

给定一个包含N个点,M条边的无向图,每条边的边权均为1。  再给定K个三元组(A,B,C),表示从A点走到B点后不能往C点走。注意三元组是有序的,如可以从B点走到A点再走到C。  现在你要在K个三元组的限制下,找出1号点到N号点的最短路径,并输出任意一条合法路径,会有Check检查你的输出。

输入输出格式

输入格式


输入文件第一行有三个数N,M,K,意义如题目所述。  接下来M行每行两个数A,B,表示A,B间有一条边。  再下面K行,每行三个数(A,B,C)描述一个三元组。

输出格式


输出文件共两行数,第一行一个数S表示最短路径长度。  第二行S+1个数,表示从1到N所经过的节点。 

输入输出样例

输入样例 #1

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

输出样例 #1

4 
1 3 2 3 4 

说明

对于40%的数据满足N≤10,M≤20,K≤5。  对于100%的数据满足N≤3000,M≤20000,K≤100000。