시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB311100.000%

문제

Для популяризации хоккея и повышения мастерства хоккейных команд Урала был организован Всеуральский турнир. Для участия в турнире были приглашены $N$ хоккейных команд из городов Урала. 

После первых двух туров, в каждом из которых каждая команда провела по одному матчу, оказалось, что команд слишком много. Организаторами турнира было решено допустить к дальнейшему участию только $K$ команд, никакие две из которых не встречались в рамках первых двух туров.

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

입력

В первой строке входного файла содержится число $N$ ($2 \leqslant N \leqslant 100\,000$, $N$ --- чётное).

Последующие $N$ строк содержат описания всех прошедших матчей. Описание каждого матча состоит из двух натуральных чисел, не превышающих $N$ --- номеров команд, игравших в матче. Первые $N/2$ из них соответствуют матчам первого тура, оставшиеся --- матчам второго тура.

Последняя строка входного файла содержит одно число $K$ ($2 \leqslant K \leqslant N$).

Гарантируется, что каждая команда сыграла ровно два матча: один в первом туре и один --- во втором.

출력

Выходной файл должен содержать либо единственное число $0$, если решения не существует, либо $K$ различных чисел --- номера отобранных команд.

제한

  • $N \leqslant 100\,000$

예제 입력 1

6
1 2
3 5
4 6
2 3
4 5
1 6
3

예제 출력 1

1 4 3

예제 입력 2

4
1 2
3 4
2 1
4 3
3

예제 출력 2

0