Falling Monkeys

There is a tree with \(n\) monkeys numbered from \(1\) to \(n\). Monkey \(1\) is attached to a branch by its tail, while every other monkey is connected to the tree either by being hooked by another monkey or by hooking another monkey with one of its two hands. Each monkey can use at most two hands to hook other monkeys. Initially the whole system is connected to the branch.

Starting from time \(0\), every second exactly one monkey will release one of the hands it is using for hooking. This may cause some monkeys (and all monkeys they support) to fall to the ground instantly (i.e. the falling time is considered immediate). When a monkey loses its connection to the branch (directly or through a chain of connections), it falls at that moment.

You are given the initial tree structure and the order of the release events. For each monkey output the time when it falls. Monkey \(1\) never falls (output \(0\) for monkey \(1\)).

Input structure:

• The first line contains an integer \(n\) \( (2 \le n \le 10^5) \) denoting the number of monkeys.
• The second line contains \(n-1\) space-separated integers. The \(i\)th integer (for \(i=2,3,\dots,n\)) indicates the monkey that is holding monkey \(i\) initially. It is guaranteed that each monkey (except monkey 1) is held by exactly one other monkey. Moreover, since each monkey has two hands at most, every monkey appears at most twice in this list.
• The third line contains \(n-1\) space-separated integers representing the release order. Each integer is the id of a monkey which will release one of its hands. When a monkey appears for the first time in the release order, it releases the child hooked by its first (i.e. left) hand; if it appears a second time, it releases the child in its second (i.e. right) hand. If a monkey has no hooked child at the time of its release event, nothing happens.

Simulation details:

• At time \(0\), the tree is intact and all monkeys (except monkey \(1\)) are connected to it.
• For each release event at time \(t\) (\(t=1,2,\dots,n-1\)): Let \(u\) be the monkey performing the release, and let \(v\) be the corresponding child (if any) that is still hooked by \(u\). If \(u\) is still connected to the branch (directly or indirectly through monkey \(1\)), then releasing the hook disconnects monkey \(v\) (and all monkeys in its subtree) from the branch. Those monkeys fall at time \(t\) (if they haven't already fallen earlier). If \(u\) is not connected at time \(t\), then the release does nothing (note that in a physically consistent system, those monkeys would already be falling as soon as their connection was lost).

Output the falling time for each monkey from \(1\) to \(n\). For monkey \(1\), output \(0\) (since it is attached by its tail). All other monkeys will eventually fall.

inputFormat

The input consists of three lines:

1. An integer \(n\) representing the number of monkeys.
2. \(n-1\) space-separated integers: for \(i=2\) to \(n\), the \(i\)th number indicates the monkey that is holding monkey \(i\).
3. \(n-1\) space-separated integers representing the order in which monkeys release one hand.

outputFormat

Output a single line containing \(n\) space-separated integers where the \(i\)th integer is the time when monkey \(i\) falls. For monkey 1, output 0.

sample

3
1 1
1 1

0 1 2