Задача #bav0002

Задача продублирована во вложении pdf

Денис и Герман вспомнили детство, отрочество, юность и зачёт в параллели A. Поэтому им показалось хорошей идеей мысленно вернуться в 2013 год и пройти карту в игре Майнкрафт. Но когда они запустили локальный сервер на порту 40539, оказалось, что карта является лабиринтом...

Более конкретно, карта — это

n

комнат. Комнаты пронумерованы от

1

до

n

. В каждой комнате могут быть две двери: левая и правая. Проходя через дверь, ребята попадают в другую комнату. В этой другой комнате тоже могут быть двери, а ещё из нее можно вернуться обратно в предыдущую комнату по тому же ходу, через который в неё пришли. Ребята начинают в комнате с номером

1

, из которой никуда нельзя вернуться. Более того, проходя через двери и обратные ходы, из любой комнаты можно дойти до любой другой, причем если не повторять комнаты на своём пути, то такой путь всегда единственен. Возможно, вы уже поняли, что лабиринт на самом деле представляется деревом.

Ребята выяснили, что выход из лабиринта появится в какой-то комнате, но в какой — заранее неизвестно. Более того, когда выход появится, в лабиринте выключится свет, а проходить через двери можно будет только 1 раз. Поэтому они решили заранее узнать структуру лабиринта. Для этого они воспользовались простой стратегией:

Если в комнате есть левая дверь, через которую они ещё не ходили, то шли через неё;

Иначе если в комнате есть правая дверь, через которую они ещё не ходили, то шли через неё;

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

В конце ребята вернулись в комнату с номером

1

и закончили исследовать лабиринт. Конечно, просто погулять по лабиринту интересно, но нужно было куда-то записывать его структуру. Для этого у ребят были книги. К сожалению, поля книг были слишком малы, чтобы нарисовать в них лабиринт явно. Поэтому игроки выписывали номера комнат в некотором порядке. Денис выписывал номер комнаты каждый раз, когда они попадали в неё впервые. Независимо от него Герман выписывал номер, если

они находятся в соответствующей комнате;

он ещё не выписывал соответствующий номер;

если в комнате есть левая дверь, то через левую дверь в этой комнате они уже должны пройти (если в комнате не было левой двери, то Герман это условие игнорировал).

Когда ребята вернулись, у них получилось две перестановки номеров комнат. Игровая карта была такова, что «выходом» было исчезновение пола и попадание в лаву, после которого игроки респавнились в «победной комнате». Конечно, ребята догадались, что они могут не проходить лабиринт и прокопали блоки под собой. После этого случая автор карты включил всем новым игрокам adventure mode и не дает исследовать карту. Теперь вам, чтобы пройти лабиринт, нужно восстановить его структуру. Вам очень повезло, ведь вам в руки попались перестановки, которые выписали Денис и Герман. Восстановите структуру лабиринта или скажите, что ребята ошиблись.

Формат входных данных

На первой строке находится единственное число

n

(

2

⩽

n

⩽

2

⋅

10

5

) — количество комнат в лабиринте. На второй строке находится перестановка из чисел от

1

до

n

— номера комнат в порядке, в котором их выписал Денис. На третьей строке находится перестановка из чисел от

1

до

n

— номера комнат в порядке, в котором их выписал Герман.

Формат выходных данных

Если не существует ровно одного лабиринта, в котором ребята могли получить данные вам перестановки, начав обход лабиринта в комнате с номером

1

, то выведите на единственной строке число

−

1

.

Если же такой лабиринт существует, то выведите

n

строк. На

i

-й строке должно находиться два числа

x

i

и

y

i

, означающие, что левая дверь из комнаты

i

ведёт в комнату

x

i

, а правая дверь ведёт в комнату

y

i

. Если какая-то дверь в комнате отсутствует, то вместо соответствующего номера (

x

i

или

y

i

) выведите число

0

.

Примеры

Входные данные

6

1 3 5 6 4 2

3 5 1 4 6 2

Выходные данные

3 6

0 0

0 5

0 0

0 0

4 2

Входные данные

2

2 1

1 2

Выходные данные

-1