AT_abc398_e [ABC398E] Tree Game

[problemUrl]: https://atcoder.jp/contests/abc398/tasks/abc398_e 本题是一道**交互题**（你的程序需要通过输入输出与评测系统进行交互）。 给定一棵包含 $N$ 个顶点的树 $G$，顶点编号为 $1$ 至 $N$。第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。 你和高桥君将使用这棵树 $G$ 进行游戏。首先，你选择先手或后手。之后，双方轮流进行以下操作（先手先行动）： - 选择一个满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，并满足以下两个条件： - $G$ 中当前不存在连接顶点 $i$ 和顶点 $j$ 的边。 - 在 $G$ 中添加连接顶点 $i$ 和顶点 $j$ 的边后，不会形成奇环。 - 将该边添加到 $G$ 中。 无法进行操作的一方判负，另一方获胜。请通过实际与高桥君对弈取得胜利。 **奇环的定义**：顶点序列 $(v_0, v_1, \ldots, v_k)$ 满足以下所有条件时，称为 $G$ 的一个奇环： - $k$ 为奇数。 - $v_0 = v_k$。 - 对所有 $1 \leq i \leq k$，存在连接 $v_{i-1}$ 和 $v_i$ 的边。 ### 交互方式 本题是一道交互题，你的程序需通过标准输入输出与评测系统交互。 首先，通过标准输入接收 $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$： > $i$ $j$ 当 $(i, j) = (-1, -1)$ 时，表示你已获胜且游戏结束，此时需立即终止程序。 其他情况下，$(i, j)$ 表示高桥君选择的整数对。

见「交互方式」。

见「交互方式」。

### 约束条件 - $2 \leq N \leq 100$ - $1 \leq U_i < V_i \leq N$ - 给定的图是树。 - 输入均为整数。 ### 注意事项 - $\footnotesize\color{red}\textsf{\textbf{每次输出后，需在末尾添加换行符并刷新标准输出缓冲区。否则可能导致评测结果为 \colorbox{#f0ad4e}{\color{white}{TLE}}。}}$ - **若在交互过程中输出格式错误或程序意外终止，评测结果将不确定。** - 游戏结束后请立即终止程序，否则评测结果不确定。 ### 交互示例 |输入|输出|解释| |:-|:-|:-| |$\begin{matrix} \texttt{4 { }} \\ \texttt{1 2} \\ \texttt{2 3} \\ \texttt{3 4} \end{matrix}$| |首先，你收到 $N$ 和 $G$ 的边信息。| ||$\texttt{First}$|你选择先手行动。| ||$\texttt{1 4}$|你在顶点 $1$ 和 $4$ 之间添加一条边| |$\texttt{-1 -1}$||高桥无法继续操作，你获胜。评测结果返回 $\colorbox{#5cb85c}{\footnotesize\textsf{\textbf{\color{white}{AC}}}}$。|