CF2204D Alternating Path

给定一个包含 $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 \times 10^5$，$0 \le m \le 2 \times 10^5$），分别表示图的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$），表示一条无向边。 输入保证： - 给定的图没有自环或重边； - 所有测试用例的 $n$ 之和不超过 $2 \times 10^5$； - 所有测试用例的 $m$ 之和不超过 $2 \times 10^5$。

对于每组测试用例，输出一个整数，表示定向后最多可以有多少个美丽顶点。

由 ChatGPT 5 翻译