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

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

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

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

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

В первой строке дано целое число N — количество вершин в найденном и любимом деревьях (2 ≤ N ≤ 10³).

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

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

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

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

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

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