Идет 5555-й год. У вас есть граф, и вы хотите найти длинный цикл и огромный независимый набор просто потому, что можете. Но пока что вы хотите найти хоть одно из двух.
Для связного графа с \(n\) вершинами вы можете или:
- найти независимое множество с ровно \(\lceil\sqrt{n}\rceil\) вершинами.
- найти простой цикл длиной не менее \(\lceil\sqrt{n}\rceil\).
Независимое множество — это множество вершин такое, что никакие две вершины из него не связаны ребром. Простой цикл — это цикл, который не содержит ни одной вершины дважды. Гарантировано, что вы всегда можете решить хотя бы одну из этих задач.
Выходные данные
Если вы решили решить первую задачу, то в первой строке выведите 1, а затем строку, содержащую \(\lceil\sqrt{n}\rceil\) различных целых чисел, не превышающих \(n\), вершины в желаемом независимом наборе.
Если вы решили решить вторую задачу, то в первой строке выведите 2, затем строку, содержащую одно целое число \(c\), представляющее длину найденного цикла, за которой следует строка, содержащая \(c\) различных целых чисел, не превышающих \(n\) — вершины в нужном цикле, в порядке, в котором они идут в цикле.
Примечание
В первом примере:
Обратите внимание, что вы можете решить обе задачи, поэтому вывод цикла \(2-4-3-1-5-6\) также является решением.
Во втором примере:
Обратите внимание, что если есть несколько ответов, вы можете вывести любой, поэтому, например, вывод цикла \(2-5-6\) разрешен.
В третьем примере:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 6
1 3
3 4
4 2
2 6
5 6
5 1
|
1
1 6 4
|
|
2
|
6 8
1 3
3 4
4 2
2 6
5 6
5 1
1 4
2 5
|
2
4
1 5 2 4
|
|
3
|
5 4
1 2
1 3
2 4
2 5
|
1
3 4 5
|