D. Alternating Path
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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?

Input

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$$$.
Output

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

Example
Input
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
Output
2
4
4
1