Coloring Game with Bonus Rounds

Alice and Bob are playing a coloring game on an undirected connected graph. The graph is constructed as follows:

1. Begin with n nodes labeled 1 to n.
2. Then, for each of m chains given by a triplet \( (u, v, l) \), do the following:
   1. If \(l = 0\), add an edge directly between nodes \(u\) and \(v\).
   2. If \(l \gt 0\), add \(l\) new nodes (named \(x^i_1, x^i_2, \ldots, x^i_{l}\) for the current chain) and add edges between \(u\) and \(x^i_1\), then between \(x^i_1\) and \(x^i_2\), ..., between \(x^i_{l-1}\) and \(x^i_l\), and finally between \(x^i_l\) and \(v\). Note that these newly added nodes are unique per chain and will not be connected to nodes from other chains.

At the start of the game, Alice colors node 1 black (representing her occupied node), and Bob colors every node in a given set \(S\) white. It is guaranteed that node 1 is not in \(S\). Then the two players take turns (Alice goes first) performing the following move:

• The current player selects one of the nodes they already occupy (Alice occupies black nodes; Bob, white nodes) and picks an adjacent uncolored node, then colors that node with their own color.
• If a player has no valid move (i.e. none of their occupied nodes have an adjacent uncolored node), they must pass.

The game ends when every node (both the original and the newly added nodes) is colored. There is also a non‐empty set \(T\) (consisting of some of the original \(n\) nodes) chosen before the game. Bob wins if, at the end of the game, every node in \(T\) is white. Otherwise (i.e. if at least one node in \(T\) is black), Alice wins.

Both players play optimally. However, Alice considers that in certain situations she has a large advantage. In order to make the game more balanced, she is willing to skip her first \(k\) moves (i.e. Bob will effectively have \(k\) additional moves before Alice plays her first move). Note that if Bob has no valid move in one of these bonus turns, he still skips his turn, even though nothing happens. Alice will only skip her first \(k\) moves; after that, she plays optimally. (Equivalently, Bob gets an extra \(k\) moves before the regular play begins.)

Your task is to determine the minimum \(k\) such that if Alice skips her first \(k\) moves, Bob is guaranteed a win. If Bob wins in the original game (with \(k=0\)), output 0. If even when \(k=1000000\) the win isn’t guaranteed for Bob under optimal play, output 1000000 instead.

Note on Game Analysis: Under optimal play the final color of every node is decided by which player can reach that node first. Think of the game as a race starting from Alice’s initial seed (node 1, with distance 0) versus Bob’s seeds (the nodes in \(S\), with distance 0) where moves alternate. In the standard game (\(k=0\)) if a node is reached with distances \(d_A\) (from node 1) and \(d_B\) (from the nearest node in \(S\)), then if \(d_A \le d_B\) the node becomes black (since Alice moves first) and otherwise white. When Alice skips her first \(k\) moves, Bob effectively reduces his distances by \(k\) (i.e. his effective reach time for any node becomes \(d_B-k\)). Thus, a node \(v\) will eventually be white if and only if \[ d_B(v)-k < d_A(v). \] Bob wins the game if every node in \(T\) satisfies this inequality. Therefore, the minimal \(k\) needed is \[ k = \max\Big(0, \max_{t \in T} \big(d_B(t) - d_A(t)\big) + 1\Big). \] If the computed \(k\) exceeds 1000000 then the answer is 1000000.

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(m\), where \(n\) (\(\ge 1\)) is the number of initial nodes and \(m\) is the number of chains.
2. The second line begins with an integer \(s\) (the size of \(S\)), followed by \(s\) distinct integers representing the nodes in the set \(S\). It is guaranteed that node 1 is not in \(S\).
3. The third line begins with an integer \(t\) (the size of \(T\)), followed by \(t\) distinct integers representing the nodes in the set \(T\) (each between 1 and \(n\)).
4. Then \(m\) lines follow. Each of these lines contains three integers \(u\), \(v\), and \(l\) describing a chain:
   • If \(l = 0\), add an edge directly between \(u\) and \(v\>.
   • If \(l > 0\), add \(l\) new nodes and form a chain connecting \(u\) and \(v\) as described above.

Note: The newly added nodes (from chains) are assigned labels starting from \(n+1\) consecutively.

outputFormat

Output a single integer representing the minimum \(k\) such that if Alice skips her first \(k\) moves, Bob will win. If Bob already wins when \(k=0\), output 0. If even with \(k = 1000000\) Bob cannot force a win, output 1000000.

sample

3 2
1 2
1 3
1 3 0
2 3 0

1