← 返回题目列表

AtCoder · abc398_e

H. 树游戏

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

这个问题是 交互问题 (其中您的程序和判断系统通过输入和输出进行通信)。

你得到一棵树 G 与 N 顶点编号 1 to N。的 i第一条边连接顶点 U_i 和 V_i.

你将使用这棵树与高桥玩游戏 G。首先,你决定谁是第一,谁是第二。然后,从第一个玩家开始,轮流执行以下操作:

  • 选择一对整数 (i,j) 与 1 \leq i < j \leq N 满足以下两个条件,则添加一条连接顶点的边 i 和 j to G.
    • G 尚无连接顶点的边 i 和 j.
    • 添加连接顶点的边 i 和 j 不会创建奇数循环。

无法执行此操作的玩家失败,另一位玩家获胜。与高桥进行这场比赛并获胜。

什么是奇数周期?

一系列顶点 当且仅当满足以下所有条件时, (v_0,v_1,\ldots,v_k) of 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

轮到高桥了,两个整数 i,j 将通过标准输入按顺序给出,并用空格分隔:

i j

If (i,j)=(-1,-1),这意味着他不能再采取行动,你就赢了。在这种情况下,请立即终止您的程序。
否则, (i,j) 是他选择的一对整数。

注释

  • 每次输出后,请务必打印换行符并刷新标准输出。否则,你可能会得到 TLE.
  • 如果产生的输出格式不正确或者程序提前结束,则判断结果是不确定的。
  • 游戏结束后,立即终止程序。否则,判定结果不确定。

示例交互

输入 输出 说明
41 22 33 4 首先,您收到 N 和边缘 来自标准输入的 G.
First 你选择先走。
1 4 您在顶点之间添加一条边 1 和 4.
-1 -1 高桥无法再移动,所以你赢了。判断结果将是 .