H. 最大流 GCD 染色

每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

题目描述

考虑一个无向图 $G$，它有 $n$ 个顶点，每条边有一个正整数容量。我们用 $\text{maxflow}(u,v)$ 表示从源点 $u$ 到汇点 $v$ 的最大流值。
我们称图 $G$ 是 好的 (good)，如果存在一个正整数 $d \ge 2$，使得 $d$ 整除所有 $n \cdot (n-1)$ 个 $\text{maxflow}(u,v)$ 的值（对所有不同顶点对 $(u,v)$）。注意，特别地，任何没有边的图都是好的。

你得到一个图，你需要对其顶点进行染色，使得对于每种颜色，由该颜色顶点诱导的子图是好的。
请找到一种使用最少颜色数的染色方案。

*由顶点集合 $S$ 诱导的子图是指：顶点集为 $S$，边集为原图中两端点都在 $S$ 中的所有边。

输入

每个测试包含多个测试用例。
第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。
接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 50$，$0 \le m \le \frac{n(n-1)}{2}$），分别表示图的顶点数和边数。

接下来 $m$ 行，每行包含三个整数 $u, v, w$（$1 \le u, v \le n$，$1 \le w \le 10^6$），表示连接顶点 $u$ 和 $v$ 的边，容量为 $w$。
保证没有自环，也没有重边。

所有测试用例的 $n^4$ 之和不超过 $50^4$。
可以证明，其他限制意味着所有测试用例的 $m$ 之和不超过 $50000$，因此无需担心输入大小。

输出

对于每个测试用例，第一行输出一个整数 $c$，表示最少需要的颜色数。
然后输出 $2c$ 行，描述染色方案。
对于每个 $1 \le i \le c$，你需要输出两行：
第一行一个整数 $k_i$，表示第 $i$ 种颜色的顶点数；
第二行 $k_i$ 个整数，表示染成第 $i$ 种颜色的顶点编号。

如果有多种方案，输出任意一种即可。

示例输入

2
5 5
1 2 2
2 3 3
3 4 4
4 5 5
5 1 6
6 7
1 2 2
1 3 2
1 4 2
2 5 1
3 5 1
4 5 1
5 6 6

示例输出

2
2
2 4
3
1 3 5
1
6
1 2 3 4 5 6

注释

第一个测试用例的答案中，第一种颜色诱导的子图没有边，第二种颜色诱导的子图只有一条容量为 $6$ 的边；因此两个子图都是好的。

第二个测试用例中，整个图是好的，因为任意两个顶点之间的 $\text{maxflow}$ 值都能被 $3$ 整除。