30594번 - Бинарные деревья 스페셜 저지다국어

문제

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

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

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

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

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

입력

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

Во второй строке даны $N-1$ целых чисел $pa_i$ --- предки вершин найденного дерева с номерами от 1 до $N-1$ $(0 \le pa_i \le N - 1)$.

Во третьей строке даны $N-1$ целых чисел $pb_i$ --- предки вершин любимого дерева с номерами от 1 до $N-1$ $(0 \le pb_i \le N - 1)$.

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

출력

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

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

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

제한

힌트