401877: GYM100551 C Bridges in a Tree

Boy Serezha has almost graduated. There are two huge tasks left: first, to pass the winter exams, and second, to write the research work. The exams are not a problem: Serezha has already tried to pass them a year ago. But the research work is much more complicated.

Serezha selected the research topic two years ago: it is the "Dynamic 2-Connectivity Problem". This is a problem about dynamically changing a graph and responding to queries like "the number of bridges in the graph at the given moment".

Serezha has invented several solutions. One of them, the simpliest one for coding, has an unpleasant subtask. Serezha wrote the code, but it seemed to be overcomplicated.

So, he wondered, if there's another simplier implementation. A shorter, but as fast as his one. To find out the answer for this question, he decided to offer this task to a University Championship.

There are only a few months left before the time to present the research work, and Serezha is going to code much more funny algorithms, and the time is running out. And if he does not manage to finish his work in time, he will have to pass the whole fifth year of study. Again.

Please help Serezha to face this unpleasant subtask.

Recall that a tree is an undirected connected graph without cycles. A bridge is an edge of an undirected graph that increases the number of its connected components when removed.

Given is a tree YourTree of N (2 ≤ N ≤ 100 000) vertices. Your task is to calculate the number of bridges in the graphs which are produced by adding sets of K_i edges to the tree YourTree.

The first line contains integers N and M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000): the number of vertices and the number of requests.

The second line contains the description of the tree YourTree: there are N - 1 integers p₂, p₃, ..., p_N separated by single spaces which represent edges (2, p₂), (3, p₃), ..., (N, p_N). It is guaranteed that these edges form a tree. You may assume that 1 ≤ p_i < i.

M requests follow, one per line. The request number i is described by a non-negative integer K_i and K_i pairs of integers 1 through N. Each pair describes an edge to be added to the tree YourTree.

The sum K_i in all requests does not exceed 100 000.

Note that the graphs may contain loops and multiple edges. Remember that a multiple edge can never be a bridge.

For each request, write a single integer: the number of bridges in the graph produced by adding the given edges to the tree YourTree.

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

4
0
2
6
5
2
4
3