题目背景

今天 ice 出去玩了。原准备与 Alice 玩游戏的 Bob 只能和 Al 玩一场博弈游戏。

题目描述

这个游戏是在树上进行的。Bob 先手。Bob 和 Al 轮流进行以下操作，首先无法操作者判负。

• 在树上标记一条未被标记过的边。满足在每一次操作之后，存在一条简单路径遍历所有标记过的边。注意：这条简单路径可以经过未标记过的边。

如果给定的树对于 Bob 有必胜方案，输出 Play now，否则输出 Restart。

输入格式

本题多测，第一行输入一个整数表示数据组数 $T$。

对于每组测试数据，第一行输入一个整数 $n$ 表示树的节点数。

接下来 $n-1$ 行，每行输入两个整数 $u,v$ 表示 $(u,v)$ 是树上的一条边。

输出格式

对于每组测试数据，输出一个字符串，大小写敏感。

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

提示

样例数据也可见附件 $\textbf{\textit{game.in}/\textit{game.out}}$。

样例解释 1

第一组数据：

先手选择边 $(2,5)$ 必胜：
若后手选择 $(1,2)$，先手选择 $(5,6)$ 可以获胜。
若后手选择 $(2,3)$，先手选择 $(5,9)$ 可以获胜。
若后手选择 $(3,4)$，先手选择 $(5,9)$ 可以获胜。
若后手选择 $(5,6)$，先手选择 $(1,2)$ 可以获胜。
若后手选择 $(5,9)$，先手选择 $(3,4)$ 可以获胜。
若后手选择 $(7,9)$，先手选择 $(2,3)$ 可以获胜。
若后手选择 $(8,9)$，先手选择 $(3,4)$ 可以获胜。
综上，无论后手选那一条边，都不会获得胜利。

第二组数据：

先手不存在必胜策略：
若先手选择 $(1,2)$，后手选择 $(2,3)$ 获胜。
若先手选择 $(2,3)$，后手选择 $(1,2)$ 获胜。

样例解释 2

各组数据详见下图，其中前两组数据与样例一相同。

数据范围

$2\leq n\leq5\times10^5$

$1\leq T\leq10^4$

$\sum n\leq1.5\times10^6$

数据保证给定的图是一棵树。

子任务

1. （8分）$n\leq6$。
2. （18分）$n\leq12,T\leq10$。
3. （6分） $n\leq28,T\leq10$。
4. （8分）$n\leq200,T\leq10$。
5. （30分）$n\leq2000,T\leq10$。
6. （6分）最多存在两个节点度数大于 $2$。
7. （12分）树的形态是一棵完全二叉树。
8. （12分）无特殊性质。