← 返回题目列表

Codeforces · 2147/H

H. Maxflow GCD 着色

中文机器翻译题面 查看原题

考虑一个无向图 $$$G$$$,其边上有 $$$n$$$ 个顶点和正整数容量。我们用 $$$\textsf{maxflow}(u, v)$$$ 表示图中从源 $$$u$$$ 到汇 $$$v$$$ 的最大流量值。我们说这样的图 $$$G$$$ 是 好 如果存在一个正整数$$$d \geq 2$$$,使得$$$d$$$除$$$\textsf{maxflow}(u, v)$$$的每个$$$n \cdot (n-1)$$$值对于$$$G$$$的不同顶点的所有对$$$(u, v)$$$。请特别注意,任何没有边的图都是好的。

给定一个图,您必须为其顶点着色,以便对于每种颜色,由该颜色的顶点诱导$$$^{\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$$$,必须输出两行:一行包含用第 $$$i$$$ 颜色着色的顶点数量 $$$k_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$$$;因此,两个子图都很好。

在第二个测试用例中,整个图很好,因为任何一对顶点之间的 $$$\mathsf{maxflow}$$$ 的值都可以被 $$$3$$$ 整除。