Рассмотрим неориентированный граф $$$G$$$ с $$$n$$$ вершинами и положительными целыми емкостями на его ребрах. Обозначим как $$$\textsf{maxflow}(u, v)$$$ значение максимального потока в графе от истока $$$u$$$ до стока $$$v$$$. Назовем такой граф $$$G$$$ хорошим, если существует положительное целое число $$$d \geq 2$$$, такое что $$$d$$$ делит каждое из $$$n \cdot (n-1)$$$ значений $$$\textsf{maxflow}(u, v)$$$ для всех пар $$$(u, v)$$$ различных вершин графа $$$G$$$. Обратите внимание, что, в частности, любой граф без ребер является хорошим.
Вам дан граф, и вам нужно раскрасить его вершины так, чтобы для каждого цвета индуцированный$$$^{\text{∗}}$$$ подграф, образованный вершинами этого цвета, был хорошим. Найдите такую раскраску с минимально возможным количеством цветов.
$$$^{\text{∗}}$$$Индуцированный подграф для множества вершин $$$S$$$ — это другой граф, вершины которого составляют $$$S$$$, а ребра — это все ребра из оригинального графа, соединяющие пары вершин в $$$S$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 50$$$, $$$0 \leq m \leq \frac{n(n-1)}{2}$$$), количество вершин и количество ребер графа.
Следующие $$$m$$$ строк каждая содержат три целых числа $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq w \leq 10^6$$$), обозначающие, что существует ребро, соединяющее вершины $$$u$$$ и $$$v$$$ с емкостью $$$w$$$. Гарантируется, что в графе нет петель или кратных ребер между одними и теми же вершинами.
Гарантируется, что сумма значений $$$n^4$$$ по всем наборам входных данных не превосходит $$$50^4$$$.
Можно показать, что из других ограничений следует, что сумма $$$m$$$ по всем наборам входных данных не превышает $$$50\,000$$$, поэтому вам не нужно беспокоиться о размере входных данных.
Для каждого набора входных данных выведите одно целое число $$$c$$$ — минимально возможное количество цветов. Затем выведите $$$2c$$$ строк, описывающих раскраску. Для каждого $$$1 \leq i \leq c$$$ вы должны вывести две строки: одну строку с целым числом $$$k_i$$$ — количеством вершин, раскрашенных в $$$i$$$-й цвет, — за которой следует одна строка с $$$k_i$$$ целыми числами — номерами вершин, раскрашенными в $$$i$$$-й цвет.
Если существует несколько решений, выведите любое из них.
25 51 2 22 3 33 4 44 5 55 1 66 71 2 21 3 21 4 22 5 13 5 14 5 15 6 6
222 431 3 5161 2 3 4 5 6
В ответе на первый набор входных данных индуцированный подграф первого цвета не имеет ребер, а индуцированный подграф второго цвета имеет только одно ребро с емкостью $$$6$$$; следовательно, оба подграфа хорошие.
Во втором наборе входных данных весь граф хороший, так как значение $$$\mathsf{maxflow}$$$ между любой парой вершин делится на $$$3$$$.
