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$$$。
输出
对于每个测试用例,输出一个整数 - 所有子图中的最大边数 糖果图.
示例
输入复制
34 41 21 32 33 47 101 21 31 42 43 44 54 65 65 76 79 101 21 33 43 74 54 65 67 87 98 9
输出复制
3 7 8
注意
在第一个测试用例中,您可以选择下图中标记的边缘。另一方面,您无法选择所有边,因为顶点 $$$3$$$ 的度数将超过 $$$2$$$。所以所有子图的最大边数是 糖果 是 $$$3$$$。
在第二个测试用例中,您可以选择下图中标记的边缘。可以证明任意一个子图 糖果 最多有 $$$7$$$ 边。
在第三个测试用例中,下图显示了具有最大可能边数的子图之一,即 糖果.