Сегодня вторник, а значит в команде Джони Солвинг снова идёт спор, кто из них Джони, а кто Солвинг. Для того, чтобы разрешить спор ребята позвали Умника. Умник дал ребятам связный граф из \(n\) вершин без петель и кратных рёбер, такой что степень каждой вершины не менее \(3\), а также дал число \(1 \leq k \leq n\). Так как Джони - громкий дурачок, то он заявил что сможет найти в этом графе простой путь длины хотя бы \(\frac{n}{k}\). Солвинг же, немного подумав, сказал, что сможет найти \(k\) простых по вершинам циклов с представителями, таких что:
- Длина каждого цикла не менее \(3\).
- Длина каждого цикла не кратна \(3\).
- В каждом цикле найдётся представитель - такая вершина, которая отсутствует во всех других выведенных циклах.
Вам нужно помочь ребятам разрешить спор, для этого по заданному графу выведите либо решение для Джони: простой путь длины хотя бы
\(\frac{n}{k}\) (
\(n\) необязательно делится на
\(k\)), либо решение для Солвинга:
\(k\) циклов, удовлетворяющих условиям выше. Если отсутствуют решения для обоих ребят - выведите
\(-1\).
Выходные данные
Выведите PATH в первой строке, если решаете задачу для Джони. Во-второй строке выведите кол-во вершин в пути \(c\) (\(c \geq \frac{n}{k}\)), а в третьей через пробел вершины в пути в порядке следования.
Выведите CYCLES в первой строке, если решаете задачу для Солвинга. Далее нужно вывести ровно \(k\) циклов в следующем формате: в первой строке выведите кол-во вершин в цикле \(c\) (\(c \geq 3\)), во второй строке выведите сам цикл в формате аналогичном пути, причем первая вершина во второй строке должна являться представителем
Выведите одно число \(-1\), если отсутствует оба решения. Кол-во выведенных чисел не должно превосходить \(10^6\). Гарантируется, что если существует хотя бы одно из решений (для Джони или Солвинга), то и существует вывод удовлетворяющий ограничению.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6 2
1 2
1 3
1 4
2 3
2 4
3 4
|
PATH
4
1 2 3 4
|
|
2
|
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
|