Задача №111633. Хоккей на Урале
Для популяризации хоккея и повышения мастерства хоккейных команд Урала был организован Всеуральский турнир. Для участия в турнире были приглашены N хоккейных команд из городов Урала.
После первых двух туров, в каждом из которых каждая команда провела по одному матчу, оказалось, что команд слишком много. Организаторами турнира было решено допустить к дальнейшему участию только K команд, никакие две из которых не встречались в рамках первых двух туров. Требуется написать программу, которая находит набор из K команд, удовлетворяющий условиям, либо выводит сообщение о том, что это сделать невозможно. В случае существования нескольких подходящих наборов необходимо найти любой из них.
В первой строке входного файла содержится число N (2 ≤ N ≤ 100 000, N — чётное).
Последующие N строк содержат описания всех прошедших матчей. Описание каждого матча состоит из двух натуральных чисел, не превышающих N — номеров команд, игравших в матче. Первые N / 2 из них соответствуют матчам первого тура, оставшиеся — матчам второго тура.
Последняя строка входного файла содержит одно число K (2 ≤ K ≤ N).
Гарантируется, что каждая команда сыграла ровно два матча: один в первом туре и один — во втором.
Выходной файл должен содержать либо единственное число 0, если решения не существует, либо K различных чисел — номера отобранных команд.
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
6 1 2 3 5 4 6 2 3 4 5 1 6 3
1 3 4
4 1 2 3 4 2 1 4 3 3
0