#3133. [Baltic2013]ballmachine

题目描述

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

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

• .jpg)

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

.jpg)

输入格式

第一行：球的个数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  

数据范围与提示