给你一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。顶点编号从 $$$1$$$ 到 $$$n$$$。该图不包含自环或多重边。
您的任务是通过为每条边选择一个方向来制作一个有向图。引导边缘后,调用顶点序列 $$$v_1, v_2, \dots, v_k$$$,其中 $$$k$$$ 可以任意大,并且任何顶点可以重复任意次数, 交替路径 如果:
- 边$$$(v_1, v_2)$$$从$$$v_1$$$指向$$$v_2$$$;
- 边$$$(v_2, v_3)$$$从$$$v_3$$$指向$$$v_2$$$;
- 边$$$(v_3, v_4)$$$从$$$v_3$$$指向$$$v_4$$$;
- 边$$$(v_4, v_5)$$$从$$$v_5$$$指向$$$v_4$$$;
- 等等。
调用顶点 $$$v$$$ 美丽 如果原始图中从顶点 $$$v$$$ 开始的所有路径(不一定简单)都是 交替 在生成的有向图中。
最多可以制作多少个顶点 美丽 引导边缘后?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 2 \cdot 10^5$$$) - 分别是图中的顶点数和边数。
以下 $$$m$$$ 行均包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$) - 图形边缘的描述。
输入的附加限制:
- 给定的图不包含自环或多重边;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$;
- 所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 可以生成的最大顶点数 美丽 调整边缘后。
示例
输入复制
48 91 31 42 32 45 66 77 88 56 84 06 21 52 31 0
输出复制
2441