该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

饿殍：明末千里行讲述了主角“良”一行人于明末崇祯五年（1632年）从华州出发前往洛阳所经历的故事。

良与满穗约定，良跟随闯军打仗，待到“洛阳城破，豚妖身死”的那一天，于立约的湖边相见。

九年之约，良穗相遇。

题目描述

两人结伴同行，从洛阳出发前去扬州寻故人。

良穗两人清楚从洛阳到扬州的地图。共有 $n$ 个城镇，洛阳位于 $1$ 号城镇，扬州位于 $n$ 号城镇。 同时共有 $m$ 条路，每条路连接不同的地点。

保证没有两条不同的路连接同一对城镇，也没有路连接一个城镇和它自己。

此外保证任意两个城镇可以经过一系列路途相互到达。

但各地依然战乱不止，仍然有一些官兵和反军处于某些城镇当中，官兵杀良冒功，反军奸淫掳掠。简单来说，共有 $k$ 群官兵和反军，第 $i$ 群官兵或反军最初位于 $s_i$ 城镇。

很明显，良穗两人并不希望遇上无恶不作的他们。

每当良穗开始移动，每群官兵或反军也会同时移动。具体来说，良穗每次移动会选择一个与当前城镇相连的路，然后走到路连接的另一个城镇，与此同时，每群官兵或反军会随机选择一条与其所在城镇相连的路，并行军到路连接的另一个城镇。

值得注意的是，由于官兵和反军不清楚对方势力的活动范围，他们只敢在距离初始城镇的最短距离不超过 $d$ 的城镇活动。

现在，良穗两人想要规划一条最短的路线，并且不会遇到任何官兵或反军。你能帮助他们吗？

注：如果良穗两人从城镇 $x$ 通过一条路移动到相连的城镇 $y$ ，而同时有一群官兵或反军从城镇 $y$ 通过相同的路行军到城镇 $x$ ，由于路途多有草丛和树林，方便隐秘，所以良穗两人不会被官兵或反军抓住。

输入格式

第一行包含一个整数 $T$ $(1\leq T\leq 10^5)$。表示测试用例的数量。

对于每一个测试用例，第一行包含三个整数 $n$, $m$, $d$ $(2\leq n\leq 2\times10^5$, $n-1\leq m\leq min\{5\times10^5,\frac{n(n-1)}{2}\}$, $1\leq d<n)$，分别表示城镇数量，路径数量，官兵和反军的活动半径。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ 。$(1\leq x_i , y_i\leq n)$ $(x_i\not=y_i)$，表示 $i$-th 路径连接着 $x_i$ 城镇和 $y_i$ 城镇。

保证，对于任意 $i\not=j$, $x_i\not= x_j$ 或 $y_i\not= y_j$。

保证任意两个城镇可以经过一系列路途相互到达。

第 $(m+2)$ 行包含几个整数。第一个整数 $k$ $(0\leq k\leq n-2)$ 代表官兵和反军的数量，接下来是 $k$ 个整数 $s_1,s_2,\dots,s_k$ $(2\leq s_i<n)$ 分别表示每群官兵或反军开始时所在的城镇。

保证所有测试用例中 $n$ 的总和不超过 $5\times 10^5$，$m$ 的总和不超过 $2\times 10^6$。

输出格式

对于每个测试用例，如果存在能够抵达扬州的路径，则在第一行输出一个整数 $p$ ，代表路线中经过的最少路径数。

在第二行，输出 $p+1$ 个整数 $z_0=1,z_1,\dots,z_p=n$，代表路线经过的城镇序列。

如果有多条不同的最短路线，输出任意一种即可。

如果不能安全抵达扬州，则输出一个整数 $-1$。

样例

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

3
1 2 3 7
-1