405438: GYM101962 J Soteros

Soteros is the biggest organized crime syndicate of Soteropolis. They are feared and respected. Members of Soteros follow a very rigid hierarchy. Sotero, the big boss, is the direct boss of some members, which in turn are direct boss of other members, and so on, like in a rooted tree structure. Therefore, Sotero is indirectly boss of the whole organization.

We can imagine a numbered rooted tree, where Sotero is represented by vertex $$$1$$$. The other $$$n - 1$$$ members are represented by numbers between $$$2$$$ and $$$n$$$. The direct boss of the $$$i$$$-th member is $$$p_i$$$. Notice that every one has exactly one direct boss, except for Sotero.

Soteropolis is a city with $$$K$$$ junctions and a bunch of two-way streets connecting pairs of these junctions. Soteros members have the culture of making themselves present on the streets. This is also true for the big boss Sotero. Every member of the organization is responsible for conducting business in at most one street of Soteropolis. More specifically, if the $$$i$$$-th member is responsible for some street, then junctions connected by this street are $$$u_i, v_i$$$.

Polo is an undercover agent working for SIA (Soteropolis Intelligence Agency) which finally got the chance to choose which member of Soteros he wants to work for. If he chooses to work for member $$$i$$$, then he will have free pass through all the streets that members (directly or indirectly) leadered by $$$i$$$ are responsible for, but he won't be able to traverse any other streets of the town.

Polo definitely want to keep a low profile, but he won't be able to do much if he can't move around the city. He asked you to make an analysis to help on his decision.

A connected region of Soteropolis is a maximal set of junctions such that for every pair of these junctions there is a path between them consisting only of streets Polo can freely traverse. In particular, an isolated junction (with no streets Polo can traverse around it) is a connected region.

For each member of Soteros, you should compute the number of connected regions Polo will be able to traverse if he chooses to work for such member.

The first line contains two integers $$$n, K$$$ ($$$2 \leq n, K \leq 10^5$$$) – the number of members of Soteros and the number of junctions of Soteropolis, respectively.

The second line contains $$$n - 1$$$ integers separated by spaces. The $$$i$$$-th of them is $$$p_{i+1}$$$ ($$$1 \leq p_{i+1} \leq i$$$) – the direct boss of the $$$(i + 1)$$$-th member.

The next $$$n$$$ lines contains two integers each. If the $$$i$$$-th of these lines contains 0 0, then the $$$i$$$-th member is responsible for no street. Otherwise, it contains two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq K$$$; $$$u_i \neq v_i$$$) – the streets which the $$$i$$$-th member is responsible for.

Two distinct members can be responsible for a street connecting the same pair of junctions $$$u_i, v_i$$$. That means they are responsible for the same street.

Output $$$n$$$ lines. The $$$i$$$-th of them should contain an integer – the number of connected regions Polo will be able to traverse if he chooses to work for member $$$i$$$.

3 3
1 2
0 0
1 2
2 3

1
1
2

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

2
4
7
6
4
6
6
6