B. Red Light Green Light
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two players, Player 001 and Player 002, are trapped in a mysterious tree-shaped battleground. Their objective is to visit the least number of nodes—because in this game, the more steps you take, the closer you are to elimination.

The game is controlled by the Squid Game Dummy, who gives each second a Green Light to move and a Red Light to stop. This ensures that both players move simultaneously when the Green Light is given. Keep in mind that both players will aim to play optimally.

Game Rules

  • Each second, a player must move one step toward the closest unvisited node they can reach. They continue moving toward it until they arrive, then proceed to the next closest unvisited node. If multiple nodes are equidistant, the player may choose any of them.
  • No Backtracking: A player can not enter a node that the other player has already visited, but he can visit his own visited nodes multiple times.
  • Collision Penalty: If both players land on the same node at the same time, they must immediately retreat and continue visiting new nodes separately, and this node can not be visited any more.
  • Waiting Rule: If a player has no available moves, they must wait until the other player finishes their movements.
  • Losing Condition: The player who visits more nodes loses the game.

The Front Man's Twist

The Front Man noticed that with an even number of nodes, the game often ends in a tie—which he finds boring. To ensure a decisive outcome, he made sure that the number of nodes in the tree is always odd.

Input
  • $$$1 \leq t \leq 10000$$$ — the number of test cases.
  • $$$3 \leq n \leq 3 \times 10^5$$$ — the number of nodes in the tree, and $$$n$$$ is always odd.
  • $$$1 \leq q \leq 3 \times 10^5$$$ — the number of queries per test case.
  • It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$3 \times 10^5$$$.
  • The first line contains an integer $$$t$$$, the number of test cases.
  • For each test case:
    • The first line contains two integers $$$n$$$ and $$$q$$$, the number of nodes in the tree and the number of queries.
    • The next $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$, indicating a road between node $$$u$$$ and node $$$v$$$.
    • The next $$$q$$$ lines contain two integers $$$x$$$ and $$$y$$$, the starting positions of the two players, with $$$x \neq y$$$.
Output
  • For each query, output "001" if Player 001 wins.
  • Otherwise, output "002" if Player 002 wins.
  • In case of a tie (both players visit the same number of nodes), output "Remake!"
Example
Input
2
3 1
1 2
2 3
3 2
5 2
1 2
2 3
3 4
4 5
1 4
1 5
Output
001
002
Remake!
Note

This is an example of a gameplay. Let's use a black dot to represent each player's current position. Each player has their own black dot. Query 1:

test case 2 query 1.
At the start (t=1), Player 2 is at Node 4, and Player 1 is at Node 1. Player 2 can choose between Node 5 or Node 3 but decides to visit Node 5 first. Player 1, on the other hand, has only one option: Node 2, so they must visit Node 2.

At time t=2: Player 2 must move toward the closest unvisited node, so they start walking toward Node 3. Player 1 also moves toward the closest unvisited node, which is Node 3.

At time t=3: All nodes have been colored and visited by at least one player, so the game ends.

Query 2:

test case 2 query 2.