[Baltic2013]ballmachine

题目描述

有一个装球机器，构造可以看作是一棵树。有下面两种操作：

• 从根放入一个球，只要下方有空位，球会沿着树滚下。如果同时有多个点可以走，那么会选择编号最小的节点所在路径的方向。比如依次在树根4放2个球，第一个球会落到1，第二个会落到3：
• 

• 从某个位置拿走一个球，那么它上方的球会落下来。比如依次拿走5, 7, 8三个球：

---

输入格式

第一行：球的个数N，操作个数Q （N, Q <= 100 000）下面N行：第i个节点的父亲。如果是根，则为0 接下来Q行：op num

1. op == 1：在根放入num个球
2. op == 2：拿走在位置num的球

---

输出格式

保证输入合法

1. op == 1：输出最后一个球落到了哪里
2. op == 2：输出拿走那个球后有多少个球会掉下来

---

样例输入

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

---

样例输出

1
3
2
2

---

提示

没有写明提示

---

题目来源

abcdabcd987提供