Sneaker 在一个巨大的迷宫中醒来，现在他想要逃离这里。

通过迷宫中每个房间里的地图，Sneaker 了解了迷宫的结构。迷宫由 $n$ 个房间组成，Sneaker 从房间 $1$ 出发，出口在房间 $n$。此外，迷宫中还有 $m$ 条双向通道，每条通道连接两个不同的房间，且每条通道的两个方向是相互独立的。

保证没有两条不同的通道连接同一对房间，也没有通道连接房间自身。

此外，保证任意两个房间之间都可以通过一系列通道到达。

Sneaker 还发现迷宫中有 $k$ 个杀手机器人。第 $i$ 个杀手机器人初始位于房间 $s_i$。显然，Sneaker 不想也不可能与这些杀手机器人相遇。

如果 Sneaker 开始移动，每个杀手机器人也会同时移动。具体来说，Sneaker 会选择当前所在房间的一条通道，并移动到通道另一侧的房间。与此同时，每个杀手机器人会随机选择其所在房间的一条通道，并移动到通道另一侧的房间。每个杀手机器人进入和离开通道的时间与 Sneaker 相同。

所有杀手机器人都会记录它们经过的通道。如果杀手机器人经过的通道与最后记录的通道相同，它可以选择从记录中删除这两次通道记录。换句话说，杀手机器人可以选择撤销一条记录。

例如，如果一个杀手机器人当前的通道记录为 $(1, 2), (2, 7), (7, 3)$，且目前位于房间 $3$，它可以选择通过一条新通道，例如 $(3, 6)$，此时它的记录将变为 $(1, 2), (2, 7), (7, 3), (3, 6)$，机器人最终位于房间 $6$。或者，它可以穿过通道 $(3, 7)$ 返回房间 $7$，此时它的记录将变为 $(1, 2), (2, 7)$。

此外，如果杀手机器人随后选择穿过一条通道回到房间 $2$，它的记录将变为 $(1, 2)$。然而，如果它直接从房间 $3$ 移动到房间 $2$，它的记录不能变为 $(1, 2)$；相反，它将变为 $(1, 2), (2, 7), (7, 3), (3, 2)$。

此外，所有杀手机器人共享同一个自毁参数 $d$。如果一个杀手机器人到达一个房间，发现其通道记录超过 $d$，它将立即自毁。如果 Sneaker 进入一个房间，发现一个杀手机器人正在自毁或已经自毁，则不视为与该机器人相遇。

现在，Sneaker 想要规划一条经过通道数量最少的路线，并确保他不会遇到任何杀手机器人。你能帮帮他吗？

注意：如果 Sneaker 正通过一条通道从房间 $x$ 移动到房间 $y$，而一个杀手机器人正通过同一条通道从房间 $y$ 移动到房间 $x$（反方向），Sneaker 不会遇到该杀手机器人，因为通道的两个方向是相互独立的。Sneaker 只知道每个杀手机器人的初始位置，但不知道它们在每一时刻的具体位置。如果一个杀手机器人和 Sneaker 同时到达房间 $n$，则认为 Sneaker 遇到了杀手机器人，无法逃离迷宫。

输入格式

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

对于每个测试用例，第一行包含三个整数 $n, m$ 和 $d$ ($2 \le n \le 2 \times 10^5, n - 1 \le m \le \min\{5 \times 10^5, \frac{n(n-1)}{2}\}, 1 \le d < n$)，分别表示迷宫中的房间数、通道数和自毁参数。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i < y_i \le n$)，表示第 $i$ 条通道连接房间 $x_i$ 和房间 $y_i$。

保证对于任意 $i \neq j$，满足 $x_i \neq x_j$ 或 $y_i \neq y_j$。

保证任意两个房间之间都可以通过一系列通道到达。

第 $(m + 2)$ 行包含若干整数。第一个整数 $k$ ($0 \le k \le n - 2$) 表示杀手机器人的数量，随后是 $k$ 个整数 $s_1, s_2, \dots, s_k$ ($2 \le 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$。

样例

样例输入 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

样例输出 1

3
1 2 3 7
-1