「ZJOI2020」染色游戏

题目描述

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

游戏规则

• 初始状态：

  • Alice 将 $1$ 号点涂成黑色（表示占领）
  • Bob 将点集 $S$ 中的所有点涂成白色（表示占领），保证 $1 \notin S$

• 轮流操作：Alice 先手，每轮中：

  • 从自己占领的点出发
  • 选择一个相邻且未染色的点
  • 占领该点并染上自己的颜色
  • 如果无合法操作，跳过回合

• 胜负判定：约定非空点集 $T$，如果游戏结束时：

  • $T$ 中所有点都是白色 ⇒ Bob 获胜
  • 否则 ⇒ Alice 获胜
  • $T$ 可能包含 $S$ 中的点和 $1$ 号点

特殊规则

Bob 想知道：如果 Alice 跳过前 $k$ 个回合（即 Bob 在 Alice 的第一回合前额外行动 $k$ 回合）后 Bob 能够获胜，求 $k$ 的最小值。

• 如果原图上 Bob 就获胜，输出 $0$
• 如果 $k = 1000000$ 时 Bob 也不能取胜，输出 $1000000$

图生成方式

由于图可能很大，用以下方式生成：

1. 初始有 $n$ 个标号为 $1$ 到 $n$ 的空图
2. 加入 $m$ 条链，第 $i$ 条链为 $(u_i, v_i, l_i)$，其中 $1 \le u_i, v_i \le n$ 且 $u_i \neq v_i$
3. 加入 $l_i$ 个新点 $x_1^i, x_2^i, \dots, x_{l_i}^i$
4. 连接边：$(u_i, x_1^i), (x_1^i, x_2^i), \dots, (x_{l_i-1}^i, x_{l_i}^i), (x_{l_i}^i, v_i)$
5. 如果 $l_i = 0$，直接连接 $(u_i, v_i)$
6. 保证 $S$ 和 $T$ 集合的点都是初始 $n$ 个点之一

输入格式

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

对于每组数据：

n m |S| |T|
u₁ v₁ l₁
u₂ v₂ l₂
...
u_m v_m l_m
s₁ s₂ ... s_{|S|}
t₁ t₂ ... t_{|T|}

约束：

• $1 \le |S| \le n − 1$, $1 \le |T| \le n$
• $n − 1 \le m \le n$
• $1 \le u_i, v_i \le n$, $0 \le l_i \le 10^6$
• $S$ 中元素：$2 \le s_i \le n$ 且不重复
• $T$ 中元素：$1 \le t_i \le n$ 且不重复
• 图连通，无自环，无重边

输出格式

输出 $C$ 行，每行一个整数表示答案。

样例

输入

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

数据范围与提示

测试点约束：

全局约束：

• $m = n$ 或 $n − 1$
• $3 \le n \le 500$
• $C \le 10000$
• $0 \le l_i \le 10^6$
• 图中不存在点数（只计算前 $n$ 个点）大于 $100$ 的环
• 最多 $10$ 组数据满足 $n > 50$
• 最多 $1000$ 组数据满足 $n > 20$