P6632 [ZJOI2020] Coloring Game

Alice and Bob are playing a coloring game. The game is played on a connected graph with $N$ vertices and $M$ edges, where $N - 1 \le M \le N$. Bob wants to trap Alice, while Alice wants to escape Bob’s encirclement. At the start of the game, Alice colors vertex $1$ black, meaning she occupies vertex $1$. Bob colors all vertices in the set $S$ white, meaning he occupies these $|S|$ vertices. It is guaranteed that $1 \notin S$. Then the two players take turns to act, with Alice moving first. On each turn, the current player may start from a vertex occupied by themselves (black for Alice, white for Bob), choose an adjacent uncolored vertex, occupy it, and color it with their own color. If there is no vertex that can be colored, the player must skip this turn. When all vertices have been colored, the game ends. Alice and Bob have agreed on a non-empty vertex set $T$ in the graph. If, when the game ends, all vertices in $T$ are colored white, then Bob has successfully trapped Alice and Bob wins. Otherwise, at least one vertex in $T$ is colored black, and Alice wins. Note that $T$ may contain vertices from $S$ and may also contain vertex $1$. Both Alice and Bob will use optimal strategies. Bob notices that in some positions, Alice has a big advantage. If Alice could voluntarily skip some of her turns at the beginning to reach a fairer position, the game would be more interesting. Bob wants to know: if Bob can win after Alice skips her first $k$ turns, what is the minimum such $k$? Alice will only skip her first $k$ turns, and in the remaining turns she will play optimally. You may understand this as Bob taking $k$ extra turns before Alice’s first move. Note that if Bob has no legal move on a turn that Alice skips, then Bob still must skip his turn according to the rules. If Bob already wins on the original graph, output $0$. If Bob still cannot win when $k = 1000000$, output $1000000$. Since the graph may be very large, it is generated in the following way. - First, generate an empty graph with $n$ vertices labeled from $1$ to $n$. - Then add $m$ chains. The $i$-th chain is denoted as $(u_i, v_i, l_i)$, where $1 \le u_i, v_i \le n$ and $u_i \neq v_i$. - First, add $l_i$ vertices, denoted as $x_1^i, x_2^i, ..., x_{l_i}^i$. - Then add undirected edges between $(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)$. - After this operation, the $l_i$ vertices added in this chain will not be connected to any other vertices, i.e. $x_1^i ... x_{l_i}^i$ from different chains are all distinct vertices. In particular, if $l_i = 0$, then no new vertices are added, and an undirected edge is added directly between $(u_i, v_i)$. It is guaranteed that all vertices in the sets $S$ and $T$ are among the initial $n$ vertices.

The first line contains an integer $C$, the number of test cases. For each test case: - The first line contains four integers $n, m, |S|, |T|$, $(1 \le |S| \le n - 1, 1 \le |T| \le n, n - 1 \le m \le n)$. - The next $m$ lines each contain three non-negative integers $u_i, v_i, l_i$, $(1 \le u_i, v_i \le n, 0 \le l_i \le 10^6)$, describing the $i$-th chain in the statement. - The next line contains $|S|$ integers $s_1 ... s_{|S|}$, the elements of the set $S$ ($2 \le s_i \le n$, all distinct). - The next line contains $|T|$ integers $t_1 ... t_{|T|}$, the elements of the set $T$ ($1 \le t_i \le n$, all distinct). That is, each test case is given in the following format: ``` n m |S||T| u_1 v_1 l_1 u_2 v_2 l_2 ··· u_m v_m l_m s_1 s_2 ··· s_|S| t_1 t_2 ··· t_|T| ``` It is guaranteed that $u_i \neq v_i$ (no self-loops), that there are no identical pairs $(u_i, v_i)$ (no multiple edges), and that the resulting graph is connected.

Output $C$ lines. For each test case, output the minimum number of turns $k$ that Alice must skip so that Bob can win. If Bob already wins on the original graph, output $0$. If Bob still cannot win when $k = 1000000$, output $1000000$.

 For $100\%$ of the testdata, $m = n$ or $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$, and it is guaranteed that the graph contains no cycle (counting only the first $n$ vertices) with more than $100$ vertices. In each test point, at most $10$ test cases satisfy $n > 50$, and at most $1000$ test cases satisfy $n > 20$. Translated by ChatGPT 5