F. Зацикливание цикла
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Kubbi - The Cairn
⠀

Вам дан неориентированный связный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ рёбрами. Граф не содержит петель и кратных рёбер.

В рамках одной операции вы выполняете по порядку следующее:

  • выбираете целое положительное число $$$k$$$ ($$$1 \le k \le n$$$);
  • выбираете число $$$s$$$ ($$$0 \le s \le \frac{n \cdot (n - 1)}{2}$$$);
  • выводите $$$s$$$ простых путей длины $$$k-1$$$ ($$$v_{i,1} \leftrightarrow v_{i,2} \leftrightarrow \ldots \leftrightarrow v_{i,k}$$$);
  • для каждого $$$i = 1$$$ до $$$s$$$ добавляете ребро $$$(v_{i,1}, v_{i,k})$$$ в граф.

Обратите внимание, что ребро, добавленное в результате какой-либо операции, может быть использовано только в будущих операциях, поскольку рёбра добавляются после вывода всех простых путей.

Сделайте граф $$$G$$$ полным не более чем за $$$2$$$ операции. В частности, $$$G$$$ должен содержать каждое ребро $$$(u, v)$$$ с $$$u \lt v$$$ ровно один раз.

Примечание: Вам предоставляются входные файлы для первых $$$10$$$ тестов этой задачи, а также $$$2$$$ программы-чекера (одна на C++, одна на Python) для проверки вашего вывода. Чекеры предполагают, что вы соблюдаете формат ввода и вывода. Вы можете скачать zip-файл из раздела «Материалы соревнования».

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n \leq 200$$$, $$$n - 1\leq m \leq n(n-1)/2$$$) — количество вершин и рёбер в $$$G$$$, соответственно.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$), представляющих ребро $$$(u_i, v_i)$$$. Граф связный и не содержит петель и кратных рёбер.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^4$$$.

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

Для каждого набора входных данных выведите следующее.

В первой строке выведите количество операций $$$op$$$ ($$$0 \le op \le 2$$$), которые вы хотите выполнить. Для каждой операции:

  • в первой строке выведите значение $$$k$$$ ($$$1 \le k \le n$$$), которое вы выбрали в операции;
  • во второй строке выведите число $$$s$$$ ($$$0 \le s \le \frac{n \cdot (n - 1)}{2}$$$) простых путей, которые вы хотите вывести;
  • в каждой из следующих $$$s$$$ строк выведите $$$k$$$ целых положительных чисел, представляющих путь $$$v_{i,1} \leftrightarrow v_{i,2} \leftrightarrow \ldots \leftrightarrow v_{i,k}$$$.
Пример
Входные данные
3
4 3
1 2
1 3
1 4
3 3
1 2
1 3
2 3
5 4
4 2
2 3
3 5
5 1
Выходные данные
2
3
1
2 1 3
4
2
4 1 2 3
4 1 3 2
0
2
4
2
4 2 3 5
2 3 5 1
3
4
4 5 1
4 5 3
2 1 5
3 2 1
Примечание

В первом наборе входных данных:

ВыводОбъяснение
$$$\texttt{2}$$$Количество операций для выполнения ($$$=2$$$).
$$$\texttt{3}$$$Операция 1.  Значение $$$k$$$ ($$$k=3$$$, пути имеют длину $$$2$$$).
$$$\texttt{1}$$$Число $$$s$$$ простых путей в этой операции ($$$s=1$$$).
$$$\texttt{2 1 3}$$$Один простой путь; когда операция заканчивается, добавляется ребро $$$(2,3)$$$.
$$$\texttt{4}$$$Операция 2.  $$$k=4$$$ (длина пути $$$3$$$).
$$$\texttt{2}$$$Будут выведены два простых пути в этой операции ($$$s=2$$$).
$$$\texttt{4 1 2 3}$$$Первый путь; после операции добавляется ребро $$$(3,4)$$$.
$$$\texttt{4 1 3 2}$$$Второй путь; после операции добавляется ребро $$$(2,4)$$$. Обратите внимание, что вывод $$$\texttt{4 3 1 2}$$$ не будет корректным, потому что он использует ребро $$$(3,4)$$$, которое появляется только после обработки обоих путей этой операции.