Рабочее место участника

Агентурная сеть из `N` агентов была организована по всем правилам: в целях конспирации каждый её агент знал лишь своих непосредственных агентов-информаторов и своего агента-куратора (которому передавал добытую информацию сам). Каждый из агентов имел уникальный позывной, выражавшийся целым числом `K` (`1\ ≤\ K\ ≤\ N`). При этом ни один куратор не являлся собственным информатором даже опосредовано, каждый информатор имел только одного непосредственного куратора и только один агент (резидент) не имел своего куратора.

В некоторый момент контрразведка раскрыла сеть и приступила к её ликвидации по следующим правилам:

1. из всех имеющихся агентов арестовывается агент-информатор с минимальным позывным;

2. агент-куратор, у которого арестованы все информаторы, рассматривается как агент- информатор.

Известно, что из всей сети не арестованными остались только двое и каждый арестованный агент успел сообщить своему куратору о провале. Современным историкам попала в руки только часть архивов разведки – список позывных кураторов, которые получили информацию о провале от своих информаторов, в порядке проведения арестов.

Необходимо восстановить весь порядок ликвидации агентурной сети.

В первой строке одно число `N` (`3\ ≤\ N\ ≤\ 1000`). Начиная со следующей строки по одному числу в строке, заданы `N-2` позывных агентов-кураторов в том порядке, в котором они получали сообщения о ликвидации своих информаторов.

Последовательность из `N-2` строк, в каждой строке по 2 позывных (через пробел): первым – позывной ликвидируемого агента, вторым – позывной агента-куратора, строки с позывными записываются в порядке проведения арестов. В N-1 строке позывные двух спасшихся агентов (через пробел), причем первым идёт позывной с меньшим значением.

8
1 4 1 6 6 4

2 1
3 4
5 1
1 6
7 6
6 4
4 8