13479번 - Gangsters in Central City 다국어

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 ≤ n ≤ 100 000; 1 ≤ q ≤ 100 000).

The second line contains the description of the sewage: a sequence of n − 1 integers p₂, p₃, . . . , p_n, where p_i is the parent of the vertex i (1 ≤ 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
.