考虑两个玩家的游戏:Alice 和 Bob。他们有一棵树$$$T$$$;最初,这棵树的每个顶点都是 白色。爱丽丝和鲍勃轮流:爱丽丝先走,然后是鲍勃,然后是爱丽丝,然后是鲍勃,依此类推。
在爱丽丝的第一回合中,她必须选择一个顶点并在其中放入一个芯片,然后绘制所选的顶点 红色。除了第一个回合外,在每个回合中,爱丽丝都必须将筹码移动到相邻的筹码中。 白色 顶点并绘制该顶点 红色。如果在爱丽丝的回合开始时,没有与有筹码的顶点相邻的白色顶点,则游戏结束。
在鲍勃的每个回合中,他必须选择一个白色顶点并绘制它 蓝色。如果鲍勃的回合开始时树中没有白色顶点,则游戏结束。
游戏的最终得分为 红色 顶点。 Alice 想要最大化分数,Bob 想要最小化分数。两名球员都发挥最佳。
这是游戏的描述。问题的陈述如下。
给你一棵树,最初只包含一个编号为 $$$1$$$ 的顶点。然后执行$$$q$$$查询;在第 $$$i$$$ 次查询期间,一个新的顶点被添加到树中;这个新顶点的编号为$$$(i+1)$$$,并通过一条边连接到顶点$$$v_i$$$。每次查询后,如果 Alice 和 Bob 在当前树上玩,则必须打印游戏的最终得分。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。
第二行包含 $$$q$$$ 整数 $$$v_1, v_2, \dots, v_q$$$ ($$$1 \le v_i \le i$$$),其中 $$$v_i$$$ 是在第 $$$i$$$ 次查询期间与顶点 $$$(i+1)$$$ 连接的顶点。
输出
打印 $$$q$$$ 整数;如果 Alice 和 Bob 在处理第 $$$i$$$ 查询后得到的树上玩,则这些整数中的第 $$$i$$$ 应该是分数。
示例
输入复制
91 1 3 3 1 2 1 2 8
输出复制
1 2 2 2 2 2 2 3 3