P7841 "C.E.L.U-03" A 100% Unfair Game

Today, ice went out to have fun. Bob, who originally planned to play a game with Alice, can only play a game of strategy with Al.

This game is played on a tree. Bob moves first. Bob and Al take turns doing the following operation. The first player who cannot make a move loses. - Mark an unmarked edge on the tree. It must satisfy that after each operation, there exists a simple path that traverses all marked edges. Note that this simple path **may pass through unmarked edges**. If the given tree has a winning strategy for Bob, output `Play now`; otherwise output `Restart`.

This problem has multiple test cases. The first line contains an integer $T$ indicating the number of test cases. For each test case, the first line contains an integer $n$ indicating the number of nodes in the tree. The next $n-1$ lines each contain two integers $u, v$ indicating that $(u, v)$ is an edge of the tree.

For each test case, output a string. The output is case-sensitive.

**The sample testdata can also be found in the attachment** $\textbf{\textit{game.in}/\textit{game.out}}$. ### Sample Explanation 1 **Test case 1:** If the first player chooses edge $(2, 5)$, they can guarantee a win: If the second player chooses $(1, 2)$, the first player can choose $(5, 6)$ to win. If the second player chooses $(2, 3)$, the first player can choose $(5, 9)$ to win. If the second player chooses $(3, 4)$, the first player can choose $(5, 9)$ to win. If the second player chooses $(5, 6)$, the first player can choose $(1, 2)$ to win. If the second player chooses $(5, 9)$, the first player can choose $(3, 4)$ to win. If the second player chooses $(7, 9)$, the first player can choose $(2, 3)$ to win. If the second player chooses $(8, 9)$, the first player can choose $(3, 4)$ to win. In summary, no matter which edge the second player chooses, they will not be able to win. **Test case 2:** The first player has no winning strategy: If the first player chooses $(1, 2)$, the second player chooses $(2, 3)$ and wins. If the first player chooses $(2, 3)$, the second player chooses $(1, 2)$ and wins. ### Sample Explanation 2 The details of each test case are shown in the figure below. The first two test cases are the same as in Sample 1.  --- ### Constraints $2\leq n\leq5\times10^5$ $1\leq T\leq10^4$ $\sum n\leq1.5\times10^6$ The testdata guarantees that the given graph is a tree. ### Subtasks 1. (8 points) $n\leq6$. 2. (18 points) $n\leq12, T\leq10$. 3. (6 points) $n\leq28, T\leq10$. 4. (8 points) $n\leq200, T\leq10$. 5. (30 points) $n\leq2000, T\leq10$. 6. (6 points) There are at most two nodes with degree greater than $2$. 7. (12 points) The tree is a perfect binary tree. 8. (12 points) No special properties. Translated by ChatGPT 5