Description

We call an undirected graph connected if there exists a path (u, v) for any two vertices u, v in an undirected graph.

A connected component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph.

Note: an isolated vertex which can not reached by any other vertices should be considered as one connected component.

Given an undirected graph G = (V, E), note that:
- G may not be connected.
- G doesn't have multiple edges and self-loops.

There are n vertices in V, denoted by 1, 2, ..., n.

Please answer the number of connected components in graph G.

Input

The first line of the input contains an integer t — the number of testcases.

The first line of each testcase contains two integers n and m — the size of V and the size of E.

Then m lines follow, each line contains two integers u_i and v_i (1 <= u_i, v_i <= n ; u_i != v_i), being an edge in E.

Restrictions

For test ID 1 (each 20 points):
- 1 <= t <= 5
- 2 <= n <= 10³
- 1 <= m <= min( n (n - 1) / 2, 2 * 10⁵)

For test ID 2-5 (each 20 points):
- 1 <= t <= 5
- 2 <= n <= 10⁵
- 1 <= m <= min( n (n - 1) / 2, 2 * 10⁵)

Output

For each testcase, output one line, which answer the number of connected components in graph G.

Remember there shouldn't be a ‘\n’ at the end of the last line of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss