You are given a rooted tree with vertices, with vertex as the root. The parent of vertex () is vertex . Each vertex has a value of either or written on it, and initially, vertex () has the value written on it.
You need to handle queries. The -th query () is as follows:
If the value written on vertex is , change it to ; if it is , change it to . After that, output the answer to the following problem:
Find the minimum number of operations required to make all vertices have the value by repeatedly performing the following operation:
Select a vertex. For every vertex on the path from vertex to the selected vertex (inclusive), change the value to if it is , and to if it is .
It can be proved that this can be achieved in a finite number of operations.
输入格式
The input is given in the following format:
All input values are integers.
输出格式
Output lines. On the -th line, output the answer to the -th query.
