AT_abc398_e [ABC398E] Tree Game

この問題は **インタラクティブな問題** （あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。 $ 1 $ から $ N $ の番号がついた $ N $ 頂点からなる木 $ G $ が与えられます。 $ i $ 番目の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。 この木 $ G $ を使って、あなたと高橋君がゲームをします。まず、あなたは先手後手を決めます。その後、先手から順に交互に以下の操作を行います。 - $ 1 \leq i < j \leq N $ を満たす整数の組 $ (i,j) $ であって、以下の条件をともに満たすものを選び、頂点 $ i $ と頂点 $ j $ を結ぶ辺を $ G $ に追加する。 - $ G $ は頂点 $ i $ と頂点 $ j $ を結ぶ辺を持たない - 頂点 $ i $ と頂点 $ j $ を結ぶ辺を $ G $ に追加しても、奇閉路ができない 操作を行えなくなった方が負けであり、負けでない方が勝ちです。実際に高橋君とゲームをして勝ってください。 奇閉路とは？ $ G $ の頂点の列 $ (v_0,v_1,\ldots,v_k) $ が以下の条件を全て満たすとき、かつ、そのときに限りこの列を $ G $ の奇閉路といいます。 - $ k $ は奇数である。 - $ v_0=v_k $ である。 - 全ての $ 1\leq i \leq k $ に対して、 $ v_{i-1} $ と $ v_{i} $ を結ぶ辺が存在する。 ### Input & Output Format この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。 最初に、 $ N $ および $ G $ の情報を標準入力から受け取ってください。以下の形式で与えられます。 > $ N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $ 次に、あなたが先手と後手のどちらを選ぶか決めてください。先手を選ぶ場合 `First`、後手を選ぶ場合 `Second` と標準出力に出力してください。 その後ゲームが始まります。 あなたの手番では、操作のために選んだ整数の組 $ (i,j) $ を、 $ i,j $ の順に空白区切りで標準出力に出力してください。 > $ i $ $ j $ 高橋君の手番では、 $ 2 $ つの整数 $ i,j $ が順に空白区切りで標準入力に与えられます。 > $ i $ $ j $ $ (i,j)=(-1,-1) $ のとき、あなたがゲームに勝利しゲームが終了したことを意味します。この場合、直ちにプログラムを終了してください。 それ以外のとき、 $ (i,j) $ は高橋君が操作のために選んだ整数の組を表します。

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。** - **対話の途中で誤った出力形式による出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。** - ゲームが終了したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。 ### 入出力例 入力 出力 説明 `41 22 33 4` まず整数 $ N $ および $ G $ の情報が与えられます。 `First` あなたは先手を選びました。 `1 4` あなたは $ (1,4) $ に対して操作を行いました。 `-1 -1` 高橋君が操作を行えなくなったためゲームを終了します。ジャッジ結果は AC になります。 ### Constraints - $ 2 \leq N \leq 100 $ - $ 1 \leq U_i < V_i \leq N $ - 与えられるグラフは木である - 入力は全て整数である