print2129. Где я?

printГде я?

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дедушка Марат живет в далеком-далеком городе Ч. Дедушка очень любит ходить в гости, иногда он уходит на несколько дней, обходя при этом очень-очень много своих друзей. Дедушка, уходя из очередного дома, всегда идет только к друзьям хозяев этого дома. К некоторым Дедушка Марат мог заходить по нескольку раз. Дедушка мог даже заходить к себе домой попить чаю с внуками. Однако Дедушка очень забывчив, поэтому он иногда попросту забывает вернуться домой. Его внуки очень волнуются за него, поэтому всегда находят его и возвращают его домой. За несколько лет внуки поняли, что прежде чем они успевают найти Дедушку Марата, он успевает обойти ровно `k` друзей (внуки тоже считаются друзьями).
Несколько дней назад Дедушка Марат снова ушел погостить, и внуков интересует, где же они могут его встретить? Помогите им узнать ответ на этот вопрос. Первая строка входного файла содержит три числа `n`, `m` и `k`, где `n` – количество домов в городе Ч., а `m` – количество пар друзей (`1\ ≤\ n\ ≤\ 1000`, `1\ ≤\ m\ ≤\ 200\ 000`, `1\ ≤\ k\ ≤\ 10^9`).
Следующие `m` строк содержат описания пар друзей, по одному на каждой строке. Описание состоит из двух чисел – номера домов, хозяева которых дружат (если хозяева дома `i` дружат с хозяевами дома `j`, то и хозяева дома `j` дружат с хозяевами дома `i`
Дедушка Марат и внуки живут в доме с номером 1.
В первой строке выходного файла должно быть число `p` – количество домов, в которых мог оказаться Дедушка Марат. Во второй строке должно быть `p` чисел  – номера домов, в которых мог оказаться Дедушка Марат, в возрастающем порядке.

Пример ввода

3 3 3
1 2
1 3
2 3

Пример вывода

3
1 2 3
Источник: neerc.ifmo.ru/school
loading