Corporate life after a hostile takeover

JanuszPol is a Polish company with a long tradition. Its finances recently turned bad, and a foreign competitor took it over. The new board decided to rebuild the company organization from scratch. Until now the structure was a plain tree.

• Exactly one executive director has no superior.
• Every other employee has exactly one direct superior, and there are no cyclic relations.

Employee $y$ is a subordinate of employee $x$ if $y$ sits below $x$ in the tree, that is, if following direct superiors upward from $y$ reaches $x$.

After the takeover the company employs the same people and stays organized as a tree, but every employee receives a different position, so the shape of the tree may change completely. The executive director keeps the position. Right now nobody dares to give orders to anyone else, because a subordinate may become a superior at any moment.

You are given the tree before the takeover and the tree after it. For every employee $x$, determine how many people were subordinates of $x$ before and remain subordinates of $x$ after.

The first line contains an integer $n$ ($2 \leq n \leq 200\,000$), the number of employees. Employees are numbered from $1$ to $n$, and employee $1$ is the executive director. The second line describes the structure before the takeover with $n-1$ numbers $a_2, a_3, \ldots, a_n$, where $a_i$ is the number of the superior of employee $i$. The third line contains $n-1$ numbers $b_2, b_3, \ldots, b_n$, where $b_i$ is the superior of employee $i$ after the takeover. Both descriptions define a proper tree rooted at $1$.

Print one line with $n$ numbers separated by spaces. The $i$-th of them is the number of people who are subordinates of employee $i$ in both trees at once.