Description
给定一个包含N个点，M条边的无向图，每条边的边权均为1。 再给定K个三元组(A,B,C)，表示从A点走到B点后不能往C点走(即路径中不能出现连续三个点为ABC)。注意三元组是有序的，如可以从B点走到A点再走到C点。 现在你要在K个三元组的限制下，找出1号点到N号点的最短路径，并输出任意一条合法路径，会有Check检查你的输出。
Input
输入文件第一行有三个数N,M,K，意义如题目所述。 接下来M行每行两个数A,B，表示A,B间有一条边。 再下面K行，每行三个数(A,B,C)描述一个三元组。
Output
输出文件共两行数，第一行一个数S表示最短路径长度。 第二行S+1个数，表示从1到N所经过的节点。
Sample Input
4 4 2 1 2 2 3 3 4 1 3 1 2 3 1 3 4
Sample Output
4 1 3 2 3 4
Data Constraint
Hint
【数据范围】 对于40%的数据满足N<=10,M<=20,K<=5。 对于100%的数据满足N<=3000,M<=20000,K<=100000。
分析：BFS暴力，不解释。
代码：
const maxn=5000000; var a:Array [0..3000,0..3000] of longint; b:array [0..3000,0..3000] of boolean; list,father,c:array [0..maxn] of longint; flag:array [0..3000] of boolean; n,m,k,x,y,head,tail,i,j:longint; begin readln(n,m,k); for i:=1 to m do begin read(x,y); b[x,y]:=true; b[y,x]:=true; end; for i:=1 to k do begin read(x,y); readln(a[x,y]); end; list[1]:=1; father[1]:=0; head:=0; tail:=1; c[1]:=0; repeat head:=head mod maxn+1; for j:=1 to n do if b[list[head],j] and (a[list[father[head]],list[head]]<>j) then begin tail:=tail mond maxn+1; list[tail]:=j; father[tail]:=head; c[tail]:=c[head]+1; if list[tail]=n then begin write(c[tail]); exit; end; end; until head=tail; end.