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.

The first line contains an integer N — the number of vertices in the found and favorite trees (2 ≤ N ≤ 10³).

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 ≤ pa_i ≤ 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 ≤ pb_i ≤ N − 1).

It is guaranteed that the given trees are binary.

In the first line, output an integer M — the number of operations used (0 ≤ M ≤ 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 ≤ v ≤ N − 1, 0 ≤ u ≤ 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.