小红的树上博弈
题号：NC313354
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一棵 n 个节点的有根树，根节点为 1。初始时所有节点都是红色。
\hspace{15pt}初始时小红位于根节点 1，她要和小紫进行一场游戏。游戏由多回合组成，每一回合中：
\hspace{23pt}\bullet 小红先移动到任意一个与她当前位置相邻的红色节点；
\hspace{23pt}\bullet 之后小紫选择任意一个与小红当前位置相邻的红色节点，将其染成紫色。
\hspace{23pt}\bullet 游戏持续进行直到一方获得胜利或一方无法操作。
\hspace{15pt}如果小红移动到了一个叶子节点，则小红获胜，反之如果直到游戏结束小红都没有移动到一个叶子节点，那么小紫获胜。
\hspace{15pt}请你判断在最优策略下，谁会获胜。

【名词解释】
\hspace{15pt}叶子节点：如果一个节点没有任何子节点（即度为 1，且不是根节点，或在只有一个节点的情况下为根节点），则称其为叶子节点。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行一个整数 n (2 \leqq n \leqq 2 \times 10^5)，表示树的节点数。
\hspace{15pt}接下来 n-1 行，每行两个整数 u, v (1 \leqq u, v \leqq n)，表示树中的一条边。保证输入构成一棵树。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^5。

输出描述:

\hspace{15pt}对于每组测试数据，新起一行。

\hspace{15pt}如果小红会获胜，请输出 \texttt{red}；否则请输出 \texttt{purple}。
示例1

输入

复制 
2
7
1 2
1 3
2 4
2 5
3 6
3 7
3
1 2
2 3

输出

复制 
red
purple