Alice 和 Bob 在玩一个染色游戏。游戏在一张 $N$ 个点 $M(N-1\le M\le N)$ 条边的连通图上进行，Bob 想要围住 Alice，而 Alice 想要逃出 Bob 的包围。

游戏开始时，Alice 将 $1$ 号点涂成了黑色表示占领了 $1$ 号点，Bob 将点集 $S$ 中的所有点涂成了白色表示占领了这 $|S|$ 个点，保证 $1$ 不在 $S$ 中。接下来两个人轮流进行操作，由 Alice 先手，每轮中轮到的玩家可以从一个被自己占领的点出发（对于 Alice 为黑色点对于 Bob 为白色点），选择一个相邻且未被染色的点，占领该点并染上自己的颜色。如果不存在可以染色的点，那么这位玩家必须跳过这个回合。当所有点都被染完色时，游戏结束。

Alice 和 Bob 约定了一个图中的非空点集 $T$，如果游戏结束时 $T$ 中的点全都涂成白色，则代表 Bob 成功围住了Alice，Bob 获胜。反之一定存在一个 $T$ 中的点被涂成黑色，那么 Alice 获胜。注意这里的 $T$ 可能会包含 $S$ 中的点和 $1$ 号点。

Alice 和 Bob 都会使用最优策略。Bob 注意到，在有些局面下，Alice 优势很大，如果能让 Alice 主动跳过 Alice 的一些行动回合来获得一个更加公平的局面，这个游戏会更有可玩性。Bob 想知道，如果 Alice 跳过前 $k$ 个回合之后自己能够获胜，那么这个 $k$ 的最小值是多少。

Alice 只会跳过 Alice 的前 $k$ 个回合，并且在剩下的回合中采用最优策略，即你可以理解为 Bob 在 Alice 的第一回合行动之前额外行动了 $k$ 个回合。注意如果 Bob 在 Alice 跳过的一个回合中没有合法行动，那么 Bob 仍需按照规则跳过自己的回合。如果在原图上就是 Bob 获胜那么输出 $0$。如果 $k=1000000$ 时 Bob 也不能取胜，则输出 $1000000$。

由于这个图可能很大，我们用如下的方式生成。

• 首先生成一个含有标号为 $1$ 到 $n$ 一共 $n$ 个点的空图。
• 接下来加入 $m$ 条链，第 $i$ 条链记作 $(u_i,v_i,l_i)$，其中 $1\le u_i,v_i\le n$且 $u_i\ne v_i$。
  • 首先我们加入 $l_i$ 个点，记作 $x_1^i,x_2^i,\dots ,x_{l_i}^i$。
  • 然后在之 $(u_i,x_1^i),(x_1^i,x_2^i),(x_2^i,x_3^i),\dots ,(x_{l_i-1}^i,x_{l_i}^i),(x_{l_i}^i,v_i)$ 间连上无向边。
  • 在这次操作之后，本轮中新加入的 $l_i$ 个点不会再与其他的点之间连边，即不同的链中的 $x_1^i\dots x_{l_i}^i$ 均为互不相同的点。特别地，如果 $l=0$，那么就不添加新点，直接在 $(u_i,v_i)$ 之间连上无向边。

保证 $S$ 集合以及 $T$ 集合的点均为一开始生成的 $n$ 个点之一。

输入格式

第一行输入一个整数 $C$，表示数据组数。

对于每组数据：

• 第一行输入四个整数 $n,m,|S|,|T|(1\le |S|\le n-1,1\le |T|\le n,n-1\le m\le n)$。
• 接下来 $m$ 行每行输入 $3$ 个非负整数 $u_i,v_i,l_i(1\le u_i,v_i\le n,0\le l_i\le {10}^6)$，表示题面中的第 $i$ 条链。
• 接下来一行输入 $|S|$ 个数 $s_1\dots s_{|S|}$ 表示 $S$ 集合中的所有元素（$2\le s_i\le n$ 且不重复）。
• 接下来一行输入 $|T|$ 个数 $t_1\dots t_{|T|}$ 表示 $T$ 集合中的所有元素（$1\le t_i\le n$ 且不重复）。

即每组数据按照如下格式输入： $$\begin{array}{rl}& nm|S||T|\\ & u_1{v}_1{l}_1\\ & u_2{v}_2{l}_2\\ & \cdots \\ & u_m{v}_m{l}_m\\ & s_1{s}_2\cdots s_{|S|}\\ & t_1{t}_2\cdots t_{|T|}\end{array}$$

保证 $u_i\ne v_i$（即没有自环），保证没有相同的 $(u_i,v_i)$ 对（即没有重边），保证给出的图是 一个连通图。

输出格式

输出 $C$ 行，对于每组测试数据，输出为了让 Bob 取胜 Alice 至少要跳过的回合数 $k$。如果在原图上就是 Bob 获胜那么输出 $0$。如果 $k=1000000$ 时 Bob 也不能取胜，则输出 $1000000$。

样例一

input

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

output

1
0
0
0
1

样例二

见附加文件中 ex_game2.in 与 ex_game2.ans。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$m=n$ 或 $n-1$，$3\le n\le 500$，$C=10000$，$0\le l_i\le {10}^6$，$1\le |S|\le n-1,1\le |T|\le n$ 且保证图中不存在点数（只计算前 $n$ 个点的数量）大于 $100$ 的环，每个测试点中最多只有 $10$ 组数据满足 $n>50$，最多只有 $1000$ 组数据满足 $n>20$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载