AT_abc398_e [ABC398E] Tree Game

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} $ .

N/A

N/A

### 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 `41 22 33 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 AC. ### 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.