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

游戏开始时，Alice 将 $1$ 号点涂成了黑色表示占领了 $1$ 号点，Bob 将点集 SS 中的所有点涂成了白色表示占领了这 $|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 \neq v_i$。
首先我们加入 $l_i$ 个点，记作 $x_1^i,x_2^i,...,x_ {l_i}^i$ 。
然后在 $(u_i,x_1^i),(x_1^i,x_2^i),(x_2^i,x_3^i),...,(x_{l_i?1}^i,x_{l_i}^i),(x_{l_i}^i,v_i)$ 之间连上无向边。
在这次操作之后，本轮中新加入的 $l_i$ 个点不会再与其他的点之间连边，即不同的链中的 $x_1^i ... 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-11 \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 ... s_{|S|}$ 表示 $S$ 集合中的所有元素 $(2 \le s_i \le n$ 且不重复)。
- 接下来一行输入 $|T|$ 个数 $t_1 ... t_{|T|}$ 表示 $T$ 集合中的所有元素 $(1 \le t_i \le n$ 且不重复)。

即每组数据按照如下格式输入：
\begin{aligned}&n\ m\ |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{aligned}
保证 $u_i \neq v_i$ （即没有自环），保证没有相同的$ (u_i,v_i)$ 对（即没有重边），保证给出的图是一个连通图。

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

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

1
0
0
0
1