/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : {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 君が勝ちます。
原案: oliverx3