409967: GYM103870 L Quantum Schmovements
Description
After seeing their rivalry, teacher has challenged Thomas and Waymo into the hardest team bonding activity eve. Rules are as follows:
- The game is to be played on a graph with $$$N$$$ nodes and $$$M$$$ edges.
- On each node there exists exactly one coin which can be picked up by reaching that node.
- Each edge connects two nodes $$$u_i$$$ and $$$v_i$$$ and has a label $$$l_i$$$.
- 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?
InputYou 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.
OutputFor each testcase, output $$$1$$$ integer per line, the maximum number of coins Thomas and Waymo can collect by moving zero or more times.
ExampleInput2 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 5Output
3 2Note
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