题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Głosowanie

某公司总裁想通过举办「柑橘星期四」来提升员工士气，但他在采购橙子还是葡萄柚之间犹豫不决，最终决定让员工们自己投票选择。

投票将按照公司层级进行。公司共有 $n$ 名员工，编号从 $1$ 到 $n$，其中编号 $1$ 是总裁。每位员工要么是管理者，要么是普通员工，总裁必然是管理者。每位管理者直接领导奇数名下属，这些下属可能是普通员工或其他管理者。普通员工没有下属。除了总裁（没有上级）外，每位员工有且仅有一位直接上级。公司层级中不存在循环。

普通员工独立决定支持橙子还是葡萄柚，而管理者则跟随其直接下属的多数意见投票。最终结果由总裁的投票决定。

Bajtazar 是橙子批发商，希望橙子能在投票中获胜。然而，他的好友 Bajtoni 是葡萄柚批发商，更希望葡萄柚胜出。于是，两个好友决定玩一场游戏：从 Bajtazar 开始，他们轮流（每次一人）挑选一名尚未被说服的普通员工，劝说其支持自己的柑橘（Bajtazar 和 Bajtoni 都极具说服力）。游戏在所有普通员工都被说服后结束。

请你帮助字节扎尔制定策略，选择员工的顺序，确保橙子最终获胜。你可以假设公司层级设计总是能让字节扎尔无论 Bajtoni 如何选择都能胜出。

交互方式

你需要编写一个程序，通过提供的库（模拟 Bajtoni 的行动）帮助 Bajtazar。

使用库的方法如下：

• C/C++: #include "glolib.h"
• Python: from glolib import daj_n, daj_przelozonego, ruch

库提供以下函数：

• daj_n()：返回整数 $n$，表示公司员工总数。
• daj_przelozonego(v)：返回编号为 $v$ $(1 < v \leq n)$ 的员工的直接上级编号，上级编号总是小于员工编号。
• ruch(x)：通知库 Bajtazar 选择编号为 $x$ 的普通员工进行说服，返回 Bajtoni 接下来选择的员工编号。若 Bajtazar 的这次选择是游戏的最后一动，程序会在调用后自动结束（假设 Bajtazar 总是最后行动）。

daj_n 和 daj_przelozonego 可多次调用。你的程序不得打开文件或使用标准输入输出，但可使用标准错误输出（stderr），不过这会消耗时间。程序将与库一起编译，命令如下：

• C++: g++ -O3 -static -std=c++17 glolib.cpp glo.cpp
• Python: python3 glo.py

注意：内存限制仅适用于你的代码，不包括库的内存使用。

示例评测程序

示例评测程序和交互库位于「文件」中。这些库的行为可能与正式评测不同，且未必符合任务假设，仅用于展示程序交互方式。

你的程序若与示例库编译，将从标准输入读取公司层级描述：先是 $n$，然后是 $n-1$ 个数 $p_{2}, \ldots, p_{n}$（用空格分隔），$p_{i}$ 表示编号 $i$ 的员工的上级编号。示例库中，字节尼总是选择未被说服的最小编号普通员工，这一策略也在样例和评测测试点中采用。示例库会输出字节扎尔和字节尼的每次行动。

样例 1

以下是样例中程序的运行流程，公司层级如下图所示：

调用	返回值	说明
daj_n()	7	$n=7$
daj_przelozonego(2)	1	$2$ 的上级是 $1$
daj_przelozonego(3)	2	$3$ 的上级是 $2$
daj_przelozonego(4)	1	$4$ 的上级是 $1$
daj_przelozonego(5)	1	$5$ 的上级是 $1$
daj_przelozonego(6)	2	$6$ 的上级是 $2$
daj_przelozonego(7)	2	$7$ 的上级是 $2$
ruch(3)	5	Bajtazar 说服 $3$，Bajtoni 说服 $5$
ruch(7)	4	Bajtazar 说服 $7$，Bajtoni 说服 $4$，此后橙子无胜算
ruch(6)		Bajtazar 说服 $6$，游戏结束，程序自动终止

若 Bajtazar 在第二步选择说服 $4$，则可确保橙子获胜。

样例 2

见附加文件下 [glo1ocen.in](file:glo1.in) 和 [glo1ocen.out](file:glo1.out)。

该样例满足 $n=19$，总裁直接领导 $3$ 名管理者，每位管理者领导 $5$ 名普通员工；

样例 3

见附加文件下 [glo2ocen.in](file:glo2ocen.in) 和 [glo2ocen.out](file:glo2ocen.out)。

该样例满足 $n=364$，每位管理者直接领导 $3$ 人，所有普通员工与总裁的层级距离相等；

样例 4

见附加文件下 [glo3ocen.in](file:glo3ocen.in) 和 [glo3ocen.out](file:glo3ocen.out)。

该样例满足 $n=200000$，公司有 $100001$ 名管理者（除总裁外，每人上级为编号小 $1$ 的管理者），$99999$ 名普通员工直接受 $100001$ 号管理者领导。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$2 \leq n \leq 13$	$20$
$2$	$2 \leq n \leq 1000$	$40$
$3$	$2 \leq n \leq 200000$	$40$