E - Tree Game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 425 点

問題文

この問題は インタラクティブな問題 （あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

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} を結ぶ辺が存在する。

制約

  • 2 \leq N \leq 100
  • 1 \leq U_i < V_i \leq N
  • 与えられるグラフは木である
  • 入力は全て整数である

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

最初に、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) は高橋君が操作のために選んだ整数の組を表します。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で誤った出力形式による出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
  • ゲームが終了したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。

入出力例

入力 出力 説明
4
1 2
2 3
3 4		 まず整数 N および G の情報が与えられます。
First あなたは先手を選びました。
1 4 あなたは (1,4) に対して操作を行いました。
-1 -1 高橋君が操作を行えなくなったためゲームを終了します。ジャッジ結果は になります。

Score : 425 points

Problem Statement

This problem is an interactive problem (in which your program and the judge system communicate via input and output).

You are given a tree G with N vertices numbered 1 to N. The i-th edge connects vertices U_i and V_i.

You will play a game with Takahashi using this tree G. First, you decide who is first and who is second. Then, starting from the first player, take turns performing the following operation:

  • Choose a pair of integers (i,j) with 1 \leq i < j \leq N that satisfies both of the following conditions, then add an edge connecting vertices i and j to G.
    • G does not already have an edge connecting vertices i and j.
    • Adding an edge connecting vertices i and j does not create an odd cycle.

A player who cannot perform this operation loses, and the other player wins. Play this game against Takahashi and win.

What is an odd cycle?

A sequence of vertices (v_0,v_1,\ldots,v_k) of G is called an odd cycle if and only if all of the following conditions are satisfied:

  • k is odd.
  • v_0=v_k.
  • For every 1\leq i \leq k, there is an edge connecting v_{i-1} and v_{i}.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq U_i < V_i \leq N
  • The given graph is a tree.
  • All input values are integers.

Interaction

This is an interactive problem (in which your program and the judge system communicate via input and output).

First, read N and the edges of G from Standard Input, given in the following format:

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Then, decide whether you go first or second. If you choose first, print First; if second, print Second.

Then, the game begins.

On your turn, output the chosen pair (i,j) by printing two integers i and j in this order, separated by a space:

i j

On Takahashi's turn, two integers i,j will be given in order, separated by a space, via Standard Input:

i j

If (i,j)=(-1,-1), it means he can no longer make a move and you win. Immediately terminate your program in this case.
Otherwise, (i,j) is the pair of integers he has chosen.

Notes

  • After each output, be sure to print a newline and flush Standard Output. Otherwise, you may get TLE.
  • If you produce output in an incorrect format or your program ends prematurely, the judge result is indeterminate.
  • Once the game finishes, terminate your program immediately. Otherwise, the judge result is indeterminate.

Sample Interaction

Input Output Explanation
4
1 2
2 3
3 4		 First, you receive N and the edges of G.
First You choose to go first.
1 4 You add an edge between vertices 1 and 4.
-1 -1 Takahashi can no longer move, so you win. The judge result will be .