分数: 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 |
高桥无法再移动,所以你赢了。判断结果将是 . |