Вам задан неориентированный граф G, состоящий из n вершин. Будем считать, что вершины этого графа пронумерованы целыми числами от 1 до n. Известно, что каждая вершина графа G соединена ребрами не менее чем с k другими вершинами этого графа. Ваша задача — найти в описанном графе простой цикл длины не менее k + 1.
Простым циклом длины d (d > 1) в графе G называется последовательность различных вершин графа v1, v2, ..., vd такая, что вершины v1 и vd соединены ребром графа, а также для любого целого i (1 ≤ i < d) вершины vi и vi + 1 соединены ребром графа.
Выходные данные
В первой строке выведите целое число r (r ≥ k + 1) — длина найденного цикла. В следующей строке выведите r различных целых чисел v1, v2, ..., vr (1 ≤ vi ≤ n) — найденный простой цикл.
Гарантируется, что ответ существует. Если существует несколько правильных ответов, разрешается вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
1 2
2 3
3 1
|
3
1 2 3
|
|
2
|
4 6 3
4 3
1 2
1 3
1 4
2 3
2 4
|
4
3 4 1 2
|