比赛场次	149
比赛名称	20120710
比赛状态	已结束比赛成绩
开始时间	2012-07-10 08:00:00
结束时间	2012-07-10 12:00:00
开放分组	全部用户
组织者	cqw
注释介绍	2012暑假培训A班

题目名称	三元限制最短路
输入输出	`patha.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	10 评测插件

用户	结果	时间	内存	得分
QhelDIV	AAAAAAAAAA	0.076 s	24.40 MiB	100
SnowDancer	AAAAAAAAAA	0.091 s	112.92 MiB	100
Citron酱	AAAAAAAAAA	0.091 s	116.74 MiB	100
kaaala	AAAAAAAAAA	0.110 s	44.66 MiB	100
czp	AAAAAAAAAA	0.124 s	72.67 MiB	100
Makazeu	AAAAAAAAAA	0.201 s	60.54 MiB	100
isabella	AAAAAAAAAA	0.287 s	73.72 MiB	100
zhangchi	AAAAAAAAAA	1.106 s	69.81 MiB	100
ZhouHang	AAAAAAAAAA	1.174 s	87.25 MiB	100
IMSL77	AAAAAAAAAA	1.203 s	124.73 MiB	100
fuhao	AAAAAAEAAE	0.149 s	100.40 MiB	80
CC	AAAAAAAEEE	0.617 s	103.38 MiB	70
王者自由	AAWAWAAWWW	0.729 s	112.63 MiB	50
TBK	C	0.000 s	0.00 MiB	0

1. 三元限制最短路

★☆ 输入文件：patha.in 输出文件：patha.out
时间限制：1 s 内存限制：128 MiB

【题目描述】

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

【输人格式】

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

【输出格式】

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

【输入样例】

4 4 2

1 2

2 3

3 4

1 3

1 2 3

1 3 4

【输出样例】

1 3 2 3 4

【数据规模】

对于 40%的数据满足 N≤10，M≤20，K≤5。

对于 100%的数据满足 N≤3000，M≤20000，K≤100000。