题目描述

《黑暗森林》是 ET-G 工作室计划推出的一款恐怖类密室逃脱游戏。

《黑暗森林》地图由 $n$ 个房间和 $n-1$ 条直接连接两个房间的道路组成，形态为一棵以 $1$ 为根的树。

为了让每位客人在多次体验该密室时都能体验到不同的感受，因此该密室的地图是动态变化的。具体的，定义 ET-G 对地图进行一次变换为：交换两个互相不为祖先的点的子树。而考虑到动态变化地图的维护费用高昂，因此每次密室体验至多只会进行一次变换。且每次交换后独立，即交换后的影响不保留。

ET-G 听说 wshcl 的胆量不小，于是邀请了 wshcl 作为《黑暗森林》建成后的首批体验者，同时考验考验 wshcl 的勇气。众所周知，单线任务在密室中是常见的。 ET-G 想变换出一条长长的走廊，试图用一路的黑暗让 wshcl 感到畏惧，因此 ET-G 需要知道进行至多一次变换后能得到的最长直径长度，将其定义为密室的恐怖水平。

《黑暗森林》正在建设中，地图初始只有一个标号为 $1$ 的点，接下来按 $2 \sim n$ 的顺序依次加入点并连边（即每次加入一个叶子）。为了时刻了解密室的水准，每次加入一个点之后你需要求出此时密室的恐怖水平。

输入格式

从文件 forest.in 中读入数据。

第一行两个正整数 $id,n$，分别表示测试点编号（若为 $0$ 则表示样例）和树的总点数。

接下来一行 $n-1$ 个整数 $a_{2 \sim n}$，表示加入点 $i$ 时 $i$ 的父亲为 $a_i \oplus V$，其中$\oplus$表示按位异或，$V$ 表示当前密室的恐怖水平。

输出格式

输出到文件 forest.out 中。

输出 $n-1$ 行，表示每次加点之后的密室的恐怖水平。

样例 #1

样例输入 #1

0 5
1 0 0 2

样例输出 #1

1
2
3
3

样例说明 #1

加入的三条边依次为 $(1,2),(1,3),(2,4),(1,5)$。

样例 #2

见选手目录下的 forest/forest2.in 与 forest/forest2.ans 。

样例 #3

见选手目录下的 forest/forest3.in 与 forest/forest3.ans 。

样例 #4

见选手目录下的 forest/forest4.in 与 forest/forest4.ans 。该样例满足特殊性质 A。

样例 #5

见选手目录下的 forest/forest5.in 与 forest/forest5.ans 。该样例满足特殊性质 B。

样例 #6

见选手目录下的 forest/forest6.in 与 forest/forest6.ans 。

数据范围

对于所有的测试数据:

• $1 \le n \le 2 \times 10^5$

• 任意时刻树的形态合法。

每个测试点的具体限制如下表所示：

特殊性质 A：相连的点编号相差不超过 $2$。

特殊性质 B：保证树以 $1$ 为根的深度不超过 $50$。

特殊性质 C：保证数据随机。