Problem Description

Given a tree, place some balls at the root. If there is an empty position below, a ball will roll down to a lower node. If there are multiple choices, it will choose the child whose subtree (rooted at that child) has the smallest minimum node label. Each position can contain at most one ball. If there is already a ball at a position, then that position is considered occupied.

When a ball is removed from a position, balls above it will also roll down.

You are given a sequence of operations: placing some balls at the root, and removing the ball at a certain node. Compute the required result after each operation.

Input Format

The first line contains two integers $N,Q$, representing the number of nodes in the tree and the number of operations.
These $N$ nodes are labeled from $1$ to $N$.
The next $N$ lines each contain one integer. The $i$-th line gives the parent of node $i$.
The next $Q$ lines each contain two integers $opt,num$:

• If $opt=1$, place $num$ balls at the root.
• If $opt=2$, remove the ball at node $num$.

Output Format

After each operation, output one result:

• If $opt=1$, output where the last ball ends up.
• If $opt=2$, output how many balls will roll down after removing that ball.

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

1
3
2
2

Hint

Constraints

For $100\%$ of the testdata, $1 \le N,Q \le 10^5$.
For $25\%$ of the testdata, each node has either $0$ or $2$ children, and the distance from every leaf to the root is the same.
For another $30\%$ of the testdata, the output for every $opt=2$ operation is always $0$.
For another $40\%$ of the testdata, there is only one $opt=1$ operation.

Notes

Translated from BalticOI 2013 Day1 A Ball Machine.

Translated by ChatGPT 5