### 问题描述 小齐有一个连通的、无向图 $G$，包含 $N$ 个顶点（标号为 $1$ 至$N$）和 $M$ 条边。图 $G$ 可能包含自环（从节点返回到自身的边），但不包含平行边（连接相同端点的多条边）。 定义 $f_G(a, b)$ 为一个布尔函数，当存在从顶点 $1$ 到顶点 $a$ 的路径，该路径经过了恰好 $b$ 条边时，$f_G(a, b)$ 为真；否则为假。如果一条边被经过多次，它在计数中也会被多次计算。 具体来说，小齐想要构建一个无向图 $G'$，使得对于所有 $a$ 和 $b$，$f_{G'}(a, b) = f_G(a, b)$。 为了完成尽可能少的工作，小齐希望构建一个尽可能小的图。因此，你的任务是计算 $G'$ 中可能的最小边数。 每个输入包含 $T$个独立解决的测试用例。保证所有测试用例中 $N$ 的总和不超过 $10^5$，$M$ 的总和不超过 $2 \times 10^5$。 ### 输入格式 输入的第一行包含整数 $T$，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $N$ 和 $M$。 接下来的 $M$ 行每行包含两个整数 $x$ 和 $y$（$1 \leq x \leq y \leq N$），表示图 $G$ 中存在一条连接 $x$ 和 $y$ 的边。 为了提高可读性，相邻的测试用例之间用空行分隔。 ### 输出格式 对于每个测试用例，输出 $G'$ 中可能的最小边数，每个结果占一行。 ### 样例输入 ``` 2 5 5 1 2 2 3 2 5 1 4 4 5 5 5 1 2 2 3 3 4 4 5 1 5 ``` ### 样例输出 ``` 4 5 ``` ### 评测数据规模 $2 \leq N \leq 10^5$，$N-1 \leq M \leq N^2 + N^2$，$1 \leq T \leq 5 \times 10^4$。