Бинарные деревья
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вадим уверен, что с помощью подобной операции возможно привести найденное бинарное дерево в изоморфное его любимому, используя не более, чем $$$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$$$. Полученное после каждой операции дерево должно быть бинарным.

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

Примеры

Входные данные
4
0 0 1
0 1 2
Выходные данные
1
2 3
Входные данные
4
2 0 0
0 3 0
Выходные данные
0