e-olymp
Yarışlar

July 9 - ADA Training

Хоккей на Урале

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

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

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

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

В первой строке содержится число n (2n105, n чётное). Следующие n строк содержат описания всех прошедших матчей. Описание каждого матча состоит из двух натуральных чисел, не превышающих n - номеров команд, игравших в матче. Первые n / 2 из них соответствуют матчам первого тура, оставшиеся - матчам второго тура.

Последняя строка содержит одно число k (2kn).

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

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

Вывести либо единственное число 0, если решения не существует, либо k различных чисел - номера отобранных команд.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
1 2
3 5
4 6
2 3
4 5
1 6
3
Çıxış verilənləri #1
1 4 3
Giriş verilənləri #2
4
1 2
3 4
2 1
4 3
3
Çıxış verilənləri #2
0
Mənbə 2013 XXV Всероссийская олимпиада по информатике, 26 марта, Задача А