Description

To attract more visitors and money to the once proud but now more or less abandoned industrial area of Maribor, the city built a race track on the site of the former Metalna factory (one of multiple large Maribor businesses that were forced to shut down in the early 1990s). The track is constructed in the form of a rooted tree of $n$ vertices. The vertices of the tree are numbered with integer numbers $0,1, \ldots, n-1$, with the root having the number $0$.

Let the race begin! Initially, there are cars at some vertices of the tree. Every second, each car moves to the adjacent vertex in the direction towards the root. At any moment, if two or more cars happen to be simultaneously at the same vertex with a number greater than $0$, they collide and cannot participate in the race any more. For vertex $0$ (the root), this rule does not hold; the root may hold any number of cars at any moment.

For each vertex $v$, output the integer $c_{v}$, which is defined as follows:

• If there was no car at vertex $v$ at the beginning of the race, $c_{v}$ is $-1$.
• Otherwise, if the car that started at vertex $v$ collides on its way to the root, then $c_{v}$ is $-1$.
• Otherwise, $c_{v}$ is the time when the car that started at vertex $v$ reaches the root.

Input format

The first line contains an integer $n$, which represents the number of vertices in the tree.

The second line contains $n-1$ integers, namely $p_{1}, p_{2}, \ldots, p_{n-1}$. For each $i \in\{1, \ldots, n-1\}$, $p_{i}$ denotes the parent of vertex $i$; it holds that $0 \leq p_{i}<i$.

The third line contains $n$ integers, namely $a_{0}, a_{1}, \ldots, a_{n-1}$. For each $i \in\{0, \ldots, n-1\}$, $a_{i}$ is either $0$ or $1$. If there is a car at vertex $i$ at the beginning of the race, then $a_{i}=1$; otherwise, $a_{i}=0$.

Output format

Print the integers $c_{0}, c_{1}, \ldots, c_{n-1}$ on a single line, separated by a single space.

Input bounds

• $1 \leq n \leq 10^{6}$.

Subtasks

1. (3 points) $n \leq 3$.
2. (5 points) $p_{i}=i-1$ for each $i \in\{1, \ldots, n-1\}$.
3. (8 points) $n \leq 500$.
4. (9 points) $n \leq 3000$.
5. (10 points) $n \leq 10^{5}$.
6. (9 points) $p_{i}=\frac{i-1}{2}$.
7. (14 points) $n \leq 2 \cdot 10^{5}$.
8. (19 points) Each vertex has at most 3 neighbors (i.e., the root has at most 3 children, and all other vertices have at most 2 children).
9. (23 points) No additional constraints.

5
0 1 1 3
0 1 1 1 1

-1 1 -1 -1 3

Vertex $0$ (the root) contained no car at the beginning of the race. It takes $1$ second for the car starting from vertex $1$ to arrive to the root, and $3$ seconds for the car starting from vertex $4$ to do the same. The cars starting from vertices 2 and $3$ collide on their way to the root (this happens at node $1$).