Мистеру Б, чтобы долететь до Луны, достаточно решить следующую задачу.
Есть полный неориентированный граф из n вершин, нужно покрыть его несколькими простыми циклами длины 3 и 4 так, чтобы каждое ребро встречалось ровно в 2 циклах.
А вы сможете отправиться на Луну?
Выходные данные
Если решения не существует, выведите -1.
Иначе в первой строке выведите одно число k (1 ≤ k ≤ n2) — количество циклов в вашем решении.
В каждой из следующих k строк выведите описание одного цикла в следующем формате: сначала выведите число m (3 ≤ m ≤ 4) — длину цикла, а затем m целых чисел v1, v2, ..., vm (1 ≤ vi ≤ n) — вершины в цикле в порядке обхода. Каждое ребро должно входить ровно в два цикла.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
2
3 1 2 3
3 1 2 3
|
|
2
|
5
|
6
3 5 4 2
3 3 1 5
4 4 5 2 3
4 4 3 2 1
3 4 2 1
3 3 1 5
|