故障机器人

题目描述

事态紧急，有 $k$ 名杀戮机器人正在寻找你，你需要规划一条逃生路径。而你目前所处的地方有 $n$ 个房间，你初始在 $1$ 号房间，需要走到 $n$ 号房间逃离。第 $i$ 个杀戮机器人在 $a_i$ 号房间（$a_i \ne 1$，且 $a_i$ 互不相等）。 $m$ 条走廊，每条走廊连接两个房间，可以通过走廊从一个房间走到另一个房间。走廊非常的黑暗，并且非常宽敞，所以你在走廊内不会被杀戮机器人发现，但房间中很明亮，所以你如果在某一时刻和没有故障的杀戮机器人处在同一个房间，你就会出局。

每一秒钟，你会选择一条连接当前所处房间的走廊并走到走廊尽头的另一个房间，机器人则是会 随机地 选择一条去走，并记录下它所经过的路径。比如一个机器人初始在 $2$ 号房间，它第一秒走了 $2\to 3$ 这条走廊到达 $3$ 号房间，那么它的路径就是 $(2,3)$，然后下一秒它继续走 $3 \to 4$ 这条走廊 ，那么路径就是 $(2,3)(3,4)$。如果某一秒和前一秒走了同一条走廊（意味着它走过去以后又往回走了），那么路径会往前删掉一条记录，比如前面在路径为 $(2,3)(3,4)$ 的情况下如果走了 $4 \to 3$ 往回，那么路径就会变成 $(2,3)$。

注意我们并不关心是不是经过重复的点，我们只关心是否有连续的两秒，机器人走了相同的走廊。

好消息是，机器人如果路径中二元组的数量超过了一个阈值 $d$，那么它就会变成故障机器人，它会在到达下一个房间之前损坏，并且再也无法检测到你。

比如当 $d=2$ 时，机器人的路径为 $(2,3)(3,4)$ 的情况下，试图走 $4\to 5$，就会在达到 $5$ 号房间前损坏，并且失去威胁。

坏消息是，你并不知道机器人是如何进行 随机选择 的，所以你得保证自己规划的路径百分之百安全，也就是说在你选择的路上，无论机器人如何移动都不会找到你。

注意：你和机器人都不能选择待在原地不动；你在 $n$ 号房间被机器人发现也会失败。（你得保证自己达到 $n$ 号房间的时候里面没有机器人才能安全逃离）

输入格式

第一行三个正整数 $n,m,d$。

接下去 $m$ 行，第 $i$ 行 $2$ 个正整数 $u_i,v_i$，描述了一条走廊连接 $u_i$ 和 $v_i$ 两个房间。（保证没有自环和重边）

然后一行一个正整数 $k$，表示机器人数量。

接下去 $k$ 行，每行一个正整数 $a_i$，表示第 $i$ 个机器人所在的初始房间号。

输出格式

如果存在一条百分百能逃出的路径，那么第一行输出一个正整数 $L$，表示需要经过的走廊数量，然后第二行输出 $L+1$ 个整数，描述你所规划的路径（如果有多种方案，优先输出长度最短的，如果依然有多种方案，那么输出字典序最小的）。

否则直接输出 $-1$ 即可。

样例

Input 1

7 8 2
1 2
2 3
3 7
2 5
5 6
3 6
1 4
4 5
1 4

Output 1

3
1 2 3 7

Input 2

7 8 2
1 2
2 3
3 7
2 5
5 6
3 6
1 4
4 5
1 5

Output 2

-1

提示说明

Constraints

子任务	$n,d\le$	$m\le$	$k\le$	特殊性质	分值
$1$	$10$	$40$	$1$	N/A	$10$
$2$	$100$	$400$	$3$
$3$	$10^5$	$5\times 10^5$	$1$
$4$			$10^5$	保证是个菊花图，并且 $n$ 在中心点	$20$
$5$				N/A	$50$

保证 $1\le a_i\le n$。

---