题目描述

给定一个包含 $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$ 所经过的节点。 。

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

4 
1 3 2 3 4 

提示

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

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