题目描述

For a long time, there were no problems with water in Central City. The sewage of the city has a form of a rooted tree: the central reservoir is situated at the root and the houses are at the leaves. The water flows from the central reservoir to the houses by the pipes that runs along the edges of the tree. Each house has an access to water.

Suddenly, gangsters captured some of the houses. As a mayor of the city you are very concerned, and you want to kick out the gangsters. So you want to stop the water flow to houses captured by the gangsters.  To do that you could clog some pipes of the sewage system. If the path from the reservoir to a house contains at least one clogged pipe, the house does not have an access to water.

You are very afraid of the gangsters, so you decided to clog up the minimal number of pipes, that it could look like an accident. At the same time, you care about the citizens, so for the chosen number of clogged pipes, you want to minimize the number of houses without gangsters and access to water.

Unfortunately, the gangsters could appear and disappear from some houses. So, you are asking the scientists about the minimum required number of clogged pipes and the minimum required number of houses without gangsters and access to water after each change in the gangsters' location.

输入格式

The first line of the input contains two integers $n$ and $q$ -- the number of vertices in the tree which represents the sewage and the number of changes in the location of the gangsters $(2 \le n \le 100 000$ ; $1 \le q \le 100 000)$ .

The second line contains the description of the sewage: a sequence of $n − 1$ integers $p_{2}, p_{3},$ . . . , $p_{n}$, where $p_{i} is$ the parent of the vertex $i (1 \le p_{i} < i)$ . The central reservoir is located at the vertex $1$ .

The next $q$ lines represent the changes in the location of the gangsters. Each change could be one of two different types:

• + v -- the gangsters capture the house at vertex $v$ ;
• - v -- the gangsters leave the house at vertex $v$ .

At the beginning all the houses are free of gangsters. All the changes form the correct sequence: the gangsters cannot capture the house if it is already captured and the gangsters could not leave the house if it is not captured.

输出格式

The output should contain 2q integers, two in each line: $c_{i}$ -- the minimum number of clogged pipes and $h_{i}$ -- the minimum number of houses without gangsters and have no access to water for the chosen $c_{i}$

.

题目大意

给出一棵含有 $n$ 个节点的，且 $1$ 为根节点的树，叶子节点都是房屋，让你在一个集合里面进行添加房屋和移除房屋的操作。

每一次添加和移除后，你将要回答下面两个问题：

1. 最少需要砍多少条边，才能使已选房屋都不能从根节点到达。

2. 在第 $1$ 问的条件下，如何砍边使从根节点点开始走不能到达的非已选房屋数目最小，输出最小值。

7 6
1 2 1 3 3 3
+ 4
+ 5
+ 6
+ 7
- 6
- 5

1 0
2 0
2 1
2 0
2 1
2 0

提示

Time limit: 2 s, Memory limit: 256 MB.