e-olymp
Змагання

July 9 - ADA Training

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

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

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

Потрібно написати програму, яка знаходить набір з k команд, який задовольняє умовам, або виводить повідомлення про те, що це зробити неможливо. У випадку існування декількох підходящих наборів необхідно знайти довільний з них.

Вхідні дані

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

Останній рядок містить одне число k (2kn).

Гарантується, що кожна команда зіграла рівно два матчі: один у першому турі і один у другому.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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
Джерело 2013 XXV Всеросійська олімпіада з інформатики, 26 березня, Задача А