CF2147H.Maxflow GCD Coloring

给定一个无向图 $G$，该图有 $n$ 个顶点，每条边都有一个正整数容量。我们定义 $\textsf{maxflow}(u, v)$ 表示从源点 $u$ 到汇点 $v$ 的最大流的值。我们称这个图 $G$ 是“好”的，如果存在一个正整数 $d \geq 2$，使得对所有不同的顶点对 $(u, v)$，$d$ 都整除 $n \cdot (n-1)$ 个 $\textsf{maxflow}(u, v)$ 的值。特别的，如果图中没有边，那么这个图也是“好”的。

现在给定一个图，你需要对它的顶点进行染色，使得对于每种颜色，由该颜色的顶点诱导出的子图都是“好”的。请找到所需颜色数最小的一种染色方案。

对 $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$，输出两行：第一行输出用第 $i$ 种颜色染色的顶点数 $k_i$，第二行输出这 $k_i$ 个顶点的编号。

如果有多种可行解，输出任意一种均可。

可视化工具链接

对于第一个测试用例，第一种颜色诱导出的子图没有边，第二种颜色诱导出的子图只有一条容量为 $6$ 的边，因此这两个子图都是“好”的。

对于第二个测试用例，整个图就是“好”的，因为任意一对顶点间的最大流值都能被 $3$ 整除。

由 ChatGPT 5 翻译