D. Цикл в графе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан неориентированный граф G, состоящий из n вершин. Будем считать, что вершины этого графа пронумерованы целыми числами от 1 до n. Известно, что каждая вершина графа G соединена ребрами не менее чем с k другими вершинами этого графа. Ваша задача — найти в описанном графе простой цикл длины не менее k + 1.

Простым циклом длины d (d > 1) в графе G называется последовательность различных вершин графа v1, v2, ..., vd такая, что вершины v1 и vd соединены ребром графа, а также для любого целого i (1 ≤ i < d) вершины vi и vi + 1 соединены ребром графа.

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

В первой строке записаны три целых числа n, m, k (3 ≤ n, m ≤ 105; 2 ≤ k ≤ n - 1) — количество вершин в графе, ребер в графе и ограничение снизу на степень вершины графа. В следующих m строках записаны пары целых чисел. В i-той строке записаны числа ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — номера вершин графа, которые соединяет i-тое ребро.

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

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

В первой строке выведите целое число r (r ≥ k + 1) — длина найденного цикла. В следующей строке выведите r различных целых чисел v1, v2, ..., vr (1 ≤ vi ≤ n) — найденный простой цикл.

Гарантируется, что ответ существует. Если существует несколько правильных ответов, разрешается вывести любой из них.

Примеры
Входные данные
3 3 2
1 2
2 3
3 1
Выходные данные
3
1 2 3
Входные данные
4 6 3
4 3
1 2
1 3
1 4
2 3
2 4
Выходные данные
4
3 4 1 2