C. Джони Солвинг
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня вторник, а значит в команде Джони Солвинг снова идёт спор, кто из них Джони, а кто Солвинг. Для того, чтобы разрешить спор ребята позвали Умника. Умник дал ребятам связный граф из $$$n$$$ вершин без петель и кратных рёбер, такой что степень каждой вершины не менее $$$3$$$, а также дал число $$$1 \leq k \leq n$$$. Так как Джони - громкий дурачок, то он заявил что сможет найти в этом графе простой путь длины хотя бы $$$\frac{n}{k}$$$. Солвинг же, немного подумав, сказал, что сможет найти $$$k$$$ простых по вершинам циклов с представителями, таких что:

  • Длина каждого цикла не менее $$$3$$$.
  • Длина каждого цикла не кратна $$$3$$$.
  • В каждом цикле найдётся представитель - такая вершина, которая отсутствует во всех других выведенных циклах.
Вам нужно помочь ребятам разрешить спор, для этого по заданному графу выведите либо решение для Джони: простой путь длины хотя бы $$$\frac{n}{k}$$$ ($$$n$$$ необязательно делится на $$$k$$$), либо решение для Солвинга: $$$k$$$ циклов, удовлетворяющих условиям выше. Если отсутствуют решения для обоих ребят - выведите $$$-1$$$.
Входные данные

Первая строка содержит три числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 2.5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$$$)

Последующие $$$m$$$ строк содержат описание рёбер графа в виде пар вершин $$$v$$$, $$$u$$$ ($$$1 \leq v, u \leq n$$$). Гарантируется, что $$$v \neq u$$$ и что все $$$m$$$ пар различны.

Гарантируется, что степень каждой вершины не менее $$$3$$$

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

Выведите PATH в первой строке, если решаете задачу для Джони. Во-второй строке выведите кол-во вершин в пути $$$c$$$ ($$$c \geq \frac{n}{k}$$$), а в третьей через пробел вершины в пути в порядке следования.

Выведите CYCLES в первой строке, если решаете задачу для Солвинга. Далее нужно вывести ровно $$$k$$$ циклов в следующем формате: в первой строке выведите кол-во вершин в цикле $$$c$$$ ($$$c \geq 3$$$), во второй строке выведите сам цикл в формате аналогичном пути, причем первая вершина во второй строке должна являться представителем

Выведите одно число $$$-1$$$, если отсутствует оба решения. Кол-во выведенных чисел не должно превосходить $$$10^6$$$. Гарантируется, что если существует хотя бы одно из решений (для Джони или Солвинга), то и существует вывод удовлетворяющий ограничению.

Примеры
Входные данные
4 6 2
1 2
1 3
1 4
2 3
2 4
3 4
Выходные данные
PATH
4
1 2 3 4
Входные данные
10 18 2
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
3 4
2 4
5 6
6 7
5 7
8 9
9 10
8 10
Выходные данные
CYCLES
4
4 1 2 3 
4
7 1 5 6