Областная олимпиада по информатике 2010 года за 9 класс | Казахстанские олимпиады

Задача B. Путешествие

Ваш друг решил отправиться в путешествие по городам страны, которых всего N. Проезд по каждой дороге занимает ровно один день. Каждый день он будет переезжать из города в город (он может возвращаться в город, в котором уже был). Определите, в каких городах он может оказаться через К дней после начала путешествия, если в первый день он выезжает из города 1.

Формат входного файла

Первая строка входного файла содержит три целых числа N, M и K (2 ≤ N ≤ 20, 1 ≤ M ≤ N (N – 1) / 2, 1 ≤ K ≤$10^9$). Следующие М строк содержат описание дорог в виде двух целых чисел – номеров городов, между которыми проходит соответствующая дорога. Города нумеруются целыми числами от 1 до N. Числа в строках разделены пробелами.

Формат выходного файла

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

Примеры

Вход

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

Выход

2 5 4 7

Вход

3 2 1 
2 1
2 3

Выход

2