Two Trees

A tree is a connected undirected acyclic graph.

You are given two rooted trees, each with \(N\) vertices. The root of the first tree is \(r_1\), and the root of the second tree is vertex \(r_2\).

Let \(S_1(v)\) denote the set of vertices \(u\) such that the path from \(r_1\) to \(u\) in the first tree passes through vertex \(v\). Similarly, let \(S_2(v)\) denote the set of vertices \(u\) such that the path from \(r_2\) to \(u\) in the second tree passes through vertex \(v\).

You are asked to find the sizes of the intersections \(S_1(v) \cap S_2(v)\) for all vertices \(1 \le v \le N\).

Input

The first line contains the integers \(N\), \(r_1\) and \(r_2\) – the number of vertices and the roots of the trees.

The second line contains the integers \(p_1[1], p_1[2], \dots, p_1[N]\). For every \(1 \le i \le N\) with \(i \neq r_1\), there is an edge between vertices \(i\) and \(p_1[i]\) in the first tree.

The third line contains the integers \(p_2[1], p_2[2], \dots, p_2[N]\). For every \(1 \le i \le N\) with \(i \neq r_2\), there is an edge between vertices \(i\) and \(p_2[i]\) in the second tree.

Note that the values of the elements \(p_1[r_1]\) and \(p_2[r_2]\) equal \(-1\).

Output

Print a single line with \(N\) numbers – the answer for each \(v\).

Example

For example, let \(N = 5\), \(r_1 = 3\), \(r_2 = 1\), and \(p_1 = [3, 3, -1, 1, 2]\), \(p_2 = [-1, 1, 2, 3, 3]\). Then the trees look like this:

• \(S_1(1) = \{1, 4\}\) and \(S_2(1) = \{1, 2, 3, 4, 5\}\). Their intersection is \(\{1, 4\}\).
• \(S_1(2) = \{2, 5\}\) and \(S_2(2) = \{2, 3, 4, 5\}\). Their intersection is \(\{2, 5\}\).
• \(S_1(3) = \{1, 2, 3, 4, 5\}\) and \(S_2(3) = \{3, 4, 5\}\). Their intersection is \(\{3, 4, 5\}\).
• \(S_1(4) = \{4\}\) and \(S_2(4) = \{4\}\). Their intersection is \(\{4\}\).
• \(S_1(5) = \{5\}\) and \(S_2(5) = \{5\}\). Their intersection is \(\{5\}\).

5 3 1
3 3 -1 1 2
-1 1 2 3 3

2 2 3 1 1

Constraints

• \(2 \le N \le 3 \cdot 10^5\)
• \(1 \le r_1, r_2 \le N\)
• \(1 \le p_1[i] \le N\), for all \(1 \le i \le N\) with \(i \neq r_1\)
• \(1 \le p_2[i] \le N\), for all \(1 \le i \le N\) with \(i \neq r_2\)
• \(p_1[r_1] = -1\) and \(p_2[r_2] = -1\). It is guaranteed that the arrays \(p_1\) and \(p_2\) form trees.

Subtasks

Let \(c(v)\) be the number of indices \(i\) for which \(p[i] = v\). A binary tree is a tree where \(c(v) = 0\) or \(c(v) = 2\) for all \(1 \le v \le N\). A path tree is a tree where \(c(v) \le 1\) for all \(1 \le v \le N\).

1. (11 points) The trees are identical, i.e. \(r_1 = r_2\) and \(p_1 = p_2\)
2. (12 points) \(N \le 3000\)
3. (13 points) Both trees are binary.
4. (17 points) Both trees are paths.
5. (21 points) The first tree is a path.
6. (26 points) No additional constraints.