시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 3 | 1 | 1 | 100.000% |
Для популяризации хоккея и повышения мастерства хоккейных команд Урала был организован Всеуральский турнир. Для участия в турнире были приглашены $N$ хоккейных команд из городов Урала.
После первых двух туров, в каждом из которых каждая команда провела по одному матчу, оказалось, что команд слишком много. Организаторами турнира было решено допустить к дальнейшему участию только $K$ команд, никакие две из которых не встречались в рамках первых двух туров.
Требуется написать программу, которая находит набор из $K$ команд, удовлетворяющий условиям, либо выводит сообщение о том, что это сделать невозможно. В случае существования нескольких подходящих наборов необходимо найти любой из них.
В первой строке входного файла содержится число $N$ ($2 \leqslant N \leqslant 100\,000$, $N$ --- чётное).
Последующие $N$ строк содержат описания всех прошедших матчей. Описание каждого матча состоит из двух натуральных чисел, не превышающих $N$ --- номеров команд, игравших в матче. Первые $N/2$ из них соответствуют матчам первого тура, оставшиеся --- матчам второго тура.
Последняя строка входного файла содержит одно число $K$ ($2 \leqslant K \leqslant N$).
Гарантируется, что каждая команда сыграла ровно два матча: один в первом туре и один --- во втором.
Выходной файл должен содержать либо единственное число $0$, если решения не существует, либо $K$ различных чисел --- номера отобранных команд.
6 1 2 3 5 4 6 2 3 4 5 1 6 3
1 4 3
4 1 2 3 4 2 1 4 3 3
0