考虑一个无向图 $$$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$$$ 颜色着色的顶点。
如果有多个解决方案,请打印其中任何一个。
示例
输入复制
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$$$ 整除。