Background

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.

Problem Description

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.

Input Format

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.

Output Format

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

2
9
9 5
2 1
9 8
3 2
5 6
7 9
4 3
5 2
3
1 2
2 3

Play now
Restart

附加两组样例详见
https://www.luogu.com.cn/paste/b6mh7ido

附加两组样例详见
https://www.luogu.com.cn/paste/b6mh7ido

Hint

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