← 返回题目列表

Codeforces · 2204/D

D. 备用路径

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

给你一个无向图,其中有 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 可以生成的最大顶点数 美丽 调整边缘后。

示例

输入
复制

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

输出
复制

2
4
4
1