← 返回题目列表

Codeforces · 2127/H

H. 23 再次崛起

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

Kiarash 正在摘草莓带回家......

一个图被称为 糖果 当且仅当其中每个顶点的度数最多为 $$$2$$$。

给你一个简单、无向、连通图 $$$G$$$,有 $$$n\le 30$$$ 个顶点,具有特殊属性: 每个顶点最多属于$$$5$$$简单循环$$$^{\text{*}}$$$.

$$$G$$$ 的所有子图$$$^{\text{†}}$$$ 的最大边数是多少 糖果?

$$$^{\text{*}}$$$简单循环是一个连通子图,其中每个顶点的度数恰好为 $$$2$$$

$$$^{\text{†}}$$$$$$G$$$ 的子图是其顶点和边是 $$$G$$$ 子集的图。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n \leq 30$$$, $$$n-1 \leq m \leq \frac{n(n-1)}{2}$$$) — 顶点数和边数。

然后是 $$$m$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$) — 第 $$$i$$$ 条边连接的两个顶点。

保证给定的图是简单且连通的,并且每个顶点最多属于$$$5$$$简单循环。

保证所有测试用例的$$$n^2$$$总和不超过$$$900$$$。

输出

对于每个测试用例,输出一个整数 - 所有子图中的最大边数 糖果图.

示例

输入
复制

3
4 4
1 2
1 3
2 3
3 4
7 10
1 2
1 3
1 4
2 4
3 4
4 5
4 6
5 6
5 7
6 7
9 10
1 2
1 3
3 4
3 7
4 5
4 6
5 6
7 8
7 9
8 9

输出
复制

3
7
8

注意

在第一个测试用例中,您可以选择下图中标记的边缘。另一方面,您无法选择所有边,因为顶点 $$$3$$$ 的度数将超过 $$$2$$$。所以所有子图的最大边数是 糖果 是 $$$3$$$。

在第二个测试用例中,您可以选择下图中标记的边缘。可以证明任意一个子图 糖果 最多有 $$$7$$$ 边。

在第三个测试用例中,下图显示了具有最大可能边数的子图之一,即 糖果.