H. 23 再度崛起

时间限制： 每个测试 $5$ 秒
内存限制： 每个测试 $1024$ MB

Kiarash 正在摘草莓带回家……

一个图被称为 candy 当且仅当其每个顶点的度数不超过 $2$。

给定一个简单、无向、连通图 $G$，顶点数 $n \le 30$，并具有一个特殊性质：每个顶点属于至多 $5$ 个简单环$^*$。

在所有 $G$ 的子图$^\dagger$中，candy 子图最多可以有多少条边？

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 50$）。接下来是每个测试用例的描述。

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

接下来 $m$ 行，第 $i$ 行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$）—— 第 $i$ 条边连接的两个顶点。

保证给定的图是简单且连通的，并且每个顶点属于至多 $5$ 个简单环。
保证所有测试用例的 $n^2$ 之和不超过 $900$。

输出
对于每个测试用例，输出一个整数 —— 所有 candy 子图中边数的最大值。

样例输入

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$。所以所有 candy 子图的最大边数为 $3$。

在第二个测试用例中，可以选择下图中标记的边。可以证明任何 candy 子图最多有 $7$ 条边。

在第三个测试用例中，下图展示了具有最大可能边数的一个 candy 子图。

$^*$ 简单环是指一个连通子图，其中每个顶点的度数恰为 $2$。
$^\dagger$ 图 $G$ 的子图是指其顶点集和边集均为 $G$ 的子集的图。