题目描述

给定一棵树，在根节点放一些球，如果下方有空位，那么它就会往下滚到下面的节点，如果有多个节点选择，它会选择 以其（即后文中提到的儿子节点）为根节点的子树中标号最小值最小 的儿子节点。

从一个位置上拿走球，上面的球也会滚下来。

每次给定一些操作，分别为在根节点放若干个球，和把某个节点的球拿走，求最后的结果。

输入格式

第一行两个整数 $N,Q$ 代表树的节点数和操作数。
这 $N$ 个节点编号为 $1$ 到 $N$。
接下来 $N$ 行每行一个整数第 $i$ 行代表第 $i$ 个节点的父节点。
接下来 $Q$ 行每行两个整数 $opt,num$：

• 如果 $opt=1$，代表在根节点放 $num$ 个球。
• 如果 $opt=2$，代表撤掉 $num$ 节点的球。

输出格式

每次操作后都需要输出一个结果：

• 如果 $opt=1$，输出最后一个球落到了哪里。
• 如果 $opt=2$，输出撤掉那个球会有多少个球滚下来。

8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8

1
3
2
2

提示

数据规模与约定

对于 $100\%$ 的数据，$1 \le N,Q \le 10^5$。
对于其中 $25\%$ 的数据，每个节点的儿子节点数只可能为 $0$ 个或 $2$ 个，且所有叶子节点到根节点的距离相同。
对于另外 $30\%$ 的数据，$opt=2$ 的操作输出的总为 $0$。
对于另外 $40\%$ 的数据，只能一个 $opt=1$ 的操作。

说明

翻译自 BalticOI 2013 Day1 A Ball Machine。