Бинарные деревья

문제

Вчера Вадим нашёл на дороге бинарное дерево $aa$ с корнем в 0 из $NN$ вершин. Однако любимым у него является бинарное дерево $bb$ с корнем в 0 из $NN$ вершин. Поэтому он решил преобразовать дерево $aa$ в дерево $bb$, используя следующую операцию:

• Выбирается произвольная вершина $vv$, кроме корня. Её поддерево, включая саму вершину, переподвешивается за другую вершину $uu$, которая не принадлежит выбранному поддереву. Результатом должно получиться бинарное дерево с корнем в 0.

Вадим уверен, что с помощью подобной операции возможно привести найденное бинарное дерево в изоморфное его любимому, используя не более, чем $NN$ преобразований. Помогите ему найти последовательность этих преобразований.

Напомним, что бинарное дерево --- это такое дерево, что каждая вершина является предком не более, чем 2 других вершин, у корня предка нет. Два корневых бинарных дерева называются изоморфными, если:

1. Эти два дерева состоят из одной вершины;
2. Количество детей у корней этих деревьев одинаковое, поддерево каждого ребёнка первого изоморфно поддереву какого-то ребёнка второго и поддерево каждого ребёнка второго изоморфно поддереву какого-то ребёнка первого.

입력

В первой строке дано целое число $NN$ --- количество вершин в найденном и любимом деревьях $(2\le N\le {10}^3)(2\; \backslash le\; N\; \backslash le\; 10^3)$.

Во второй строке даны $N-1N-1$ целых чисел $p{a}_{i}pa\_i$ --- предки вершин найденного дерева с номерами от 1 до $N-1N-1$ $(0\le p{a}_i\le N-1)(0\; \backslash le\; pa\_i\; \backslash le\; N\; -\; 1)$.

Во третьей строке даны $N-1N-1$ целых чисел $p{b}_{i}pb\_i$ --- предки вершин любимого дерева с номерами от 1 до $N-1N-1$ $(0\le p{b}_i\le N-1)(0\; \backslash le\; pb\_i\; \backslash le\; N\; -\; 1)$.

Гарантируется, что данные деревья бинарные.

출력

В первой строке выведите целое число $MM$ --- количество использованных операций $(0\le M\le N)(0\; \backslash le\; M\; \backslash le\; N)$.

В следующих $MM$ строках выведите пары чисел $vv$ и $uu$ --- корень выбранного поддерева и вершина, за которую это поддерево подвешивается во время текущей операции $(1\le v\le N-1,0\le u\le N-1)(1\; \backslash le\; v\; \backslash le\; N\; -\; 1,\; 0\; \backslash le\; u\; \backslash le\; N\; -\; 1)$. Вершина $uu$ не может находиться в поддереве вершины $vv$. Полученное после каждой операции дерево должно быть бинарным.

Гарантируется, что ответ существует. Если ответов несколько, выведите любой из них.

4
0 0 1
0 1 2

1
2 3

4
2 0 0
0 3 0

0