题目描述

Vadim 在路上捡到了一棵以顶点 $0$ 为根、包含 $N$ 个顶点的二叉树 $a$。但他最喜欢的是另一棵同样以顶点 $0$ 为根、包含 $N$ 个顶点的二叉树 $b$。

他希望使用下列操作，将树 $a$ 变成一棵与树 $b$ 同构的树：

• 选择一个不是根的顶点 $v$；
• 将以 $v$ 为根的整棵子树（包含 $v$ 本身）从原父亲处断开；
• 再把它挂到另一个顶点 $u$ 下面，其中 $u$ 不能位于 $v$ 的子树中；
• 操作后得到的树仍必须是一棵以 $0$ 为根的二叉树。

Vadim 确信，使用不超过 $N$ 次操作，一定可以把树 $a$ 变成一棵与树 $b$ 同构的树。

请输出一组满足要求的操作序列。

二叉树指每个顶点至多有两个儿子的有根树，根没有父亲。

两棵有根二叉树同构，当且仅当满足以下递归定义：

1. 两棵树都只包含一个顶点；或者
2. 两棵树根节点的儿子数相同，并且第一棵树的每个儿子子树都能与第二棵树的某个儿子子树一一对应且同构。

儿子的左右次序不重要。

输入格式

第一行输入一个整数 $N$，表示两棵树的顶点数：

第二行输入 $N-1$ 个整数 $pa_i$，依次表示树 $a$ 中顶点 $1,2,\ldots,N-1$ 的父亲：

第三行输入 $N-1$ 个整数 $pb_i$，依次表示树 $b$ 中顶点 $1,2,\ldots,N-1$ 的父亲：

保证输入的两棵树均为二叉树。

输出格式

第一行输出一个整数 $M$，表示使用的操作次数：

接下来输出 $M$ 行，每行两个整数 $v,u$，表示在当前操作中：

• 选择以顶点 $v$ 为根的子树；
• 将它重新挂到顶点 $u$ 下方。

必须满足：

顶点 $u$ 不能位于顶点 $v$ 的子树中，并且每次操作完成后，当前树都必须仍为二叉树。

保证答案存在。若有多种答案，输出任意一种。

样例 1

4
0 0 1
0 1 2

1
2 3

样例 2

4
2 0 0
0 3 0

0

数据范围

• 时间限制：$1$ 秒；
• 空间限制：$256$ MiB。

特殊判题说明

本题为构造题，合法答案不唯一，必须使用特殊判题程序检查：

• 操作次数是否不超过 $N$；
• 每次操作是否合法；
• 中间过程是否始终保持二叉树；
• 最终树是否与目标树同构。