#748. [Baltic2013]ballmachine

[Baltic2013]ballmachine

Description

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

  • 从根放入一个球,只要下方有空位,球会沿着树滚下。如果同时有多个点可以走,那么会选择编号最小的节点所在路径的方向。比如依次在树根4放2个球,第一个球会落到1,第二个会落到3image
  • 从某个位置拿走一个球,那么它上方的球会落下来。比如依次拿走5, 7, 8三个球: image

Format

Input

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

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

Output

保证输入合法

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

Samples

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