405559: GYM101992 G Robots race

The Yousry brothers are participating in a robots competition. The competition arena can be represented as a weighted connected undirected graph with no self-loops or multiple edges containing $$$N$$$ nodes and $$$M$$$ edges. A robot's memory can be illustrated as a stack. For a robot to be ready for the competition it needs to execute $$$Q$$$ commands of three types very efficiently.

1. Clear the robot's memory.
2. Push node $$$u$$$ to the top of the robot's memory.
3. Pop the node at the top from the robot's memory. If the memory is empty just ignore the command.

After each command of type 2 a robot should report whether the sequence of nodes in its memory is valid or not according to the following rules:

1. If the sequence consists of a single node, then it is valid.
2. If there is a node that appears more than once, then the sequence is not valid .
3. If there is a consecutive pair of nodes in the sequence that don't have an edge between them in the graph representing the arena, then the sequence is not valid .
4. If the set of edges between each two consecutive nodes in the sequence can't be a subset of the edges of some minimum spanning tree of the graph, then the sequence is not valid .
5. If non of the above three cases happen, then the sequence is valid .

Since the speed of a robot in the race depends on how fast these commands are executed, the two brothers asked you to use your algorithmic and competitive programming skills to help them win this race.

The first line of the input contains a single integer $$$T$$$ the number of test cases.

Each test case starts with a line containing three integers $$$N$$$, $$$M$$$, and $$$Q$$$, where $$$2 \leq N \leq 10^5$$$, $$$1 \leq M \leq 10^5$$$ and $$$1 \leq Q \leq 10^5$$$.

The next $$$M$$$ lines represent the edges in the graph where each line contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ to indicate an edge with weight $$$w$$$ between nodes $$$u$$$ and $$$v$$$, where $$$1 \leq u \leq N$$$, $$$1 \leq v \leq N$$$, $$$1 \leq w \leq 10^4$$$ and $$$u \neq v$$$.

The next $$$Q$$$ lines represent the commands. Each command starts with an integer $$$t$$$ the type of the command and if $$$t$$$ is 2, another integer $$$u$$$ will follow, where $$$1 \leq t \leq 3$$$ and $$$1 \leq u \leq N$$$.

For each test case, for each command of type 2 print 'y' if the sequence of nodes is valid or 'n' otherwise.

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

y
y
n
y
n
y
n

Please note that the set of minimum spanning tree edges that determine the validity doesn't have to be the same for each command. You just need to check that if you added zero or more edges from the original graph to the set of edges between each two consecutive nodes in the sequence, you will obtain one of the minimum spanning trees of the graph.