Вчера Вадим нашёл на дороге бинарное дерево $$$a$$$ с корнем в 0 из $$$N$$$ вершин. Однако любимым у него является бинарное дерево $$$b$$$ с корнем в 0 из $$$N$$$ вершин. Поэтому он решил преобразовать дерево $$$a$$$ в дерево $$$b$$$, используя следующую операцию:
Вадим уверен, что с помощью подобной операции возможно привести найденное бинарное дерево в изоморфное его любимому, используя не более, чем $$$N$$$ преобразований. Помогите ему найти последовательность этих преобразований.
Напомним, что бинарное дерево — это такое дерево, что каждая вершина является предком не более, чем 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$$$. Полученное после каждой операции дерево должно быть бинарным.
Гарантируется, что ответ существует. Если ответов несколько, выведите любой из них.
40 0 10 1 2
1 2 3
42 0 00 3 0
0