J. Binary Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yesterday, Vadim found a binary tree $$$a$$$ with root at 0 consisting of $$$N$$$ vertices on the road. However, his favorite is binary tree $$$b$$$ with root at 0 also consisting of $$$N$$$ vertices. Therefore, he decided to transform tree $$$a$$$ into tree $$$b$$$ using the following operation:

  • An arbitrary vertex $$$v$$$, other than the root, is chosen. Its subtree, including the vertex itself, is reattached to another vertex $$$u$$$, which does not belong to the chosen subtree. The result must be a binary tree with root at 0.

Vadim is confident that it is possible to transform the found binary tree into an isomorphic one to his favorite using no more than $$$N$$$ transformations. Help him find the sequence of these transformations.

Recall that a binary tree is a tree in which each vertex is the ancestor of no more than 2 other vertices, and the root has no ancestor. Two rooted binary trees are called isomorphic if:

  1. Both trees consist of a single vertex;
  2. The number of children of the roots of these trees is the same, the subtree of each child of the first is isomorphic to the subtree of some child of the second, and the subtree of each child of the second is isomorphic to the subtree of some child of the first.
Input

The first line contains an integer $$$N$$$ — the number of vertices in the found and favorite trees $$$(2 \le N \le 10^3)$$$.

The second line contains $$$N-1$$$ integers $$$pa_i$$$ — the ancestors of the vertices of the found tree numbered from 1 to $$$N-1$$$ $$$(0 \le pa_i \le N - 1)$$$.

The third line contains $$$N-1$$$ integers $$$pb_i$$$ — the ancestors of the vertices of the favorite tree numbered from 1 to $$$N-1$$$ $$$(0 \le pb_i \le N - 1)$$$.

It is guaranteed that the given trees are binary.

Output

In the first line, output an integer $$$M$$$ — the number of operations used $$$(0 \le M \le N)$$$.

In the following $$$M$$$ lines, output pairs of numbers $$$v$$$ and $$$u$$$ — the root of the chosen subtree and the vertex to which this subtree is attached during the current operation $$$(1 \le v \le N - 1, 0 \le u \le N - 1)$$$. The vertex $$$u$$$ cannot be in the subtree of vertex $$$v$$$. The tree obtained after each operation must be binary.

It is guaranteed that a solution exists. If there are multiple solutions, output any of them.

Examples
Input
4
0 0 1
0 1 2
Output
1
2 3
Input
4
2 0 0
0 3 0
Output
0