CF2204D.Alternating Path

You are given an undirected graph with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$. The graph contains no self-loops or multiple edges.

Your task is to make a graph directed by choosing a direction for each edge. After directing the edges, call a sequence of vertices $v_1, v_2, \dots, v_k$, where $k$ can be arbitrarily large and any vertex can be repeated any number of times, an alternating path if:

• the edge $(v_1, v_2)$ is directed from $v_1$ to $v_2$;
• the edge $(v_2, v_3)$ is directed from $v_3$ to $v_2$;
• the edge $(v_3, v_4)$ is directed from $v_3$ to $v_4$;
• the edge $(v_4, v_5)$ is directed from $v_5$ to $v_4$;
• and so on.

Call a vertex $v$ beautiful if all paths (not necessarily simple) in the original graph that start at vertex $v$ are alternating in the resulting directed graph.

What is the maximum number of vertices that can be made beautiful after directing the edges?

给你一个包含 $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$ 出发的路径（不一定是简单路径）在所得的有向图中均为交替路径。

在对边进行定向后，最多能有多少个顶点被设为优美的？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$; $0 \le m \le 2 \cdot 10^5$) — the number of vertices and edges in the graph, respectively.

Each of the following $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$) — the description of the edges of the graph.

Additional constraints on the input:

• The given graph contains no self-loops or multiple edges;
• The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$;
• The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single integer — the maximum number of vertices that can be made beautiful after directing the edges.

对于每个测试用例，输出一个整数——在对边进行定向后，能够变为“美丽”的顶点的最大数量。