Дідусь Марат живе у далекому-далекому місті Ч. Дідусь дуже полюбляє ходити в гості, іноді він йде на декілька днів, обходячи при цьому дуже-дуже багато своїх друзів. Дідусь, йдучи з чергового будинку, завжди йде лише до друзів хазяїв цього ж будинку. До деяких Дідусь Марат міг заходити по декілька разів. Дідусь міг навіть заходити до себе додому попити чаю з онуками. Проте Дідусь дуже забудькуватий, тому він іноді просто забуває повернутись додому. Його онуки дуже хвилюються за нього, тому завжди знаходять його і повертають його додомоу. За декілька років онуки зрозуміли, що до того, як вони встигають знайти Дідуся Марата, він встигає обійти рівно k друзів (онуки також вважаються друзями).
Декілька днів назад Дідусь Марат знову пішов погостювати, і онуків цікавить, де ж вони можуть його зустріти? Допоможіть їм взнати відповідь на це питання.
Перший рядок вхідного файлу містить три числа n, m і k, де n - кількість будинків у місті Ч., а m - кількість пар друзів (1 ≤ n ≤ 1000, 1 ≤ m ≤ 200000, 1 ≤ k ≤ 10^9).
Наступні m рядків містять описи пар друзів, по одному у кожному рядку. Опис складається з двох чисел - номери будинків, хазяї яких дружать (якщо хазяї будинку i дружать з хазями будинку j, то і хазяїа будинку j дружать з хазяями будинку i.
Дідусь Марат і онуки живуть у будинку з номером 1.
У першому рядку вихідного файлу повинно бути число p - кількість будинків, у яких міг опинитсья Дідусь Марат. У другому рядку повинно бути p чисел - номери будинків, у яких міг опинитись Дідусь Марат, у зростаючому порядку.