← 返回题目列表

AtCoder · tkppc6_1_p

P. 彩色树上的游戏

中文机器翻译题面 查看原题

配点 : {700} 点

問題文

N 顶点 1,2,\ldots,N 组成的树。i 真正的边是顶点 连接 A_i 和边缘 B_i ,C_i = B 为蓝色;C_i = R 被漆成红色。

FirstBlue 和 SecondRed 将使用这棵树玩游戏。 FirstBlue 从你开始,2 人们轮流玩。在每个回合中,执行以下操作:

  • FirstBlue 轮到你了:还剩左边。青色侧面 1 选择一个并从树中删除该边。
  • SecondRed 轮到你了:还剩下。赤色侧面 1 选择一个并从树中删除该边。

每回合,树 它分为 2 ,但在顶部 不包含 1 的树将被删除。

第一个无法执行任何操作的人失败。2 找出当人们采取最佳行动时谁会获胜。

1 对于每个输入文件, 解决T 测试用例。

制約

  • 1 \leq T \leq 3000
  • 1 \leq N \leq 40
  • 1 \leq A_i, B_i \leq N
  • C_i 是 您也可以写 B 或 至少 R
  • T, N, A_i, B_i 是一个整数
  • 给定的图是一棵树

入力

输入是按以下格式从标准输入给出的。输入的 1 该行如下。

T

并且, 当按T 测试用例如下。其中每一个都以以下格式给出。

N
A_1 B_1 C_1
\vdots
A_{N-1} B_{N-1} C_{N-1}

出力

对于每个测试用例,如果您获胜,则为 FirstBlue First ,SecondRed,如果你赢了 输出 Second 。为每个测试用例编写一个新行。


入力例 1

3
3
1 2 B
2 3 R
6
1 2 B
2 3 R
1 4 B
4 5 R
1 6 R
5
1 2 B
2 3 R
1 4 R
4 5 B

出力例 1

First
Second
Second

1 第二场比赛,FirstBlue 领先。 如果选择连接 1, 2 的边并执行操作,顶点 该树将仅包含 1 。此时,SecondRed 无法执行任何操作,因为没有剩余的红色边。因此,FirstBlue 你赢了。
2, 3 在第二场比赛中,无论FirstBlue如何行动,只要SecondRed行动得当,SecondRed就一定会获胜。

原案: 奥利弗x3