409967: GYM103870 L Quantum Schmovements

After seeing their rivalry, teacher has challenged Thomas and Waymo into the hardest team bonding activity eve. Rules are as follows:

1. The game is to be played on a graph with $$$N$$$ nodes and $$$M$$$ edges.
2. On each node there exists exactly one coin which can be picked up by reaching that node.
3. Each edge connects two nodes $$$u_i$$$ and $$$v_i$$$ and has a label $$$l_i$$$.
4. The $$$i$$$'th edge can only be crossed (in either direction) by a person if another person is standing on node $$$l_i$$$. So imagine a pressure plate on node $$$l_i$$$ that must be stood on for the entire time a person is trying to cross.

If Thomas starts on node $$$t$$$ and Waymo starts on node $$$w$$$, what is the maximum number of coins they can obtain after any finite amount of moves?

You will have to answer multiple testcases. The first line contains an integer $$$T$$$, denoting the number of testcases $$$(1 \leq T \leq 10^4)$$$.

The first line of each testcase contains two integers $$$N$$$ and $$$M$$$, $$$(1 \leq N \leq 2 \cdot 10^5), (0 \leq M \leq 5 \cdot 10^5)$$$

The following line contains two integers $$$t$$$ and $$$w$$$ $$$(1 \leq t, w \leq N)$$$, denoting the nodes that Thomas and Waymo start on respectively.

The next $$$M$$$ lines each contain $$$3$$$ integers $$$u$$$, $$$v$$$, and $$$l$$$ $$$(1 \leq u \neq v, l, \leq N)$$$ denoting an edge connected nodes $$$u$$$ and $$$v$$$ with label $$$l$$$.

It is guaranteed the graph does not have any multiedges.

It is also guaranteed the sum of $$$N$$$ does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$M$$$ does not exceed $$$5 \cdot 10^5$$$.

For tests $$$1 - 3$$$, $$$(1 \leq N \leq 16)$$$ and the sum of $$$N$$$ will not exceed $$$50$$$.

For tests $$$4 - 10$$$, the sum of $$$N$$$ will not exceed $$$3366$$$.

The remaining test cases do not satisfy any additional constraints.

For each testcase, output $$$1$$$ integer per line, the maximum number of coins Thomas and Waymo can collect by moving zero or more times.

2
5 5
1 2
1 2 2
3 2 1
1 3 2
2 4 4
4 5 5
5 5
4 5
1 2 2
3 2 1
1 3 2
2 4 4
4 5 5

3
2

In the first test case, Thomas can collect the coin on node $$$1$$$ and Waymo can collect the coin on node $$$2$$$. Then Thomas can move from node $$$1 \rightarrow 3$$$ and collect the coin on node $$$3$$$. It is impossible to collect any more coins, so the answer is $$$3$$$.

In the second test case, Thomas can collect the coin on node $$$4$$$ and Waymo can collect the coin on node $$$5$$$. Note that Thomas cannot move from node $$$4$$$ to node $$$2$$$, since Waymo is not on node $$$4$$$ to satisfy the $$$l = 4$$$ constraint. By the same logic, Waymo cannot move to node $$$4$$$. Thomas also has the choice to move to node $$$5$$$, but there is nothing gained from such a move. The final answer is $$$2$$$.

—

Idea: Timothy

Preparation: Timothy, 3366

Occurrences: Novice 11, Intermediate 9, Advanced 5