Binary Trees

Yesterday Vadim found a binary tree $a$ rooted at 0 with $N$ vertices on the road. His favorite, however, is a binary tree $b$ rooted at 0 with $N$ vertices. So he decided to turn $a$ into $b$ with the following operation:

• Pick any vertex $v$ other than the root. Its subtree, including $v$ itself, is reattached below a vertex $u$ that does not belong to the chosen subtree. The result must be a binary tree rooted at 0.

Vadim is sure that this operation can turn the tree he found into a tree isomorphic to his favorite, using at most $N$ operations. Help him find the sequence of operations.

A binary tree is a tree in which each vertex is an ancestor of at most 2 other vertices, and the root has no ancestor.

Two rooted binary trees are isomorphic if one of the following holds:

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

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

The second line contains $N-1$ integers $pa_i$, the parents of vertices $1$ to $N-1$ in the found tree ($0 \le pa_i \le N-1$).

The third line contains $N-1$ integers $pb_i$, the parents of vertices $1$ to $N-1$ in the favorite tree ($0 \le pb_i \le N-1$).

It is guaranteed that both trees are binary.

On the first line, print the number of operations $M$ ($0 \le M \le N$).

Then print $M$ lines, each with two integers $v$ and $u$: the root of the chosen subtree and the vertex it is reattached to during that operation ($1 \le v \le N-1$, $0 \le u \le N-1$). Vertex $u$ cannot lie in the subtree of $v$. The tree after each operation must be binary.

An answer is guaranteed to exist. If several answers exist, print any of them.