Minimizing Edges#11217

Minimizing Edges

1 second

128 megabytes

Very hard

Bessie has a connected, undirected graph $G$ with $n$ vertices labeled $1, 2, \dots, n$ 1, 2, \ldots, n and $m$ edges. The graph $G$ may contain self-loops (edges from a node back to itself), but no parallel edges (no multiple edges between the same pair of nodes).

Let $f_{G} (a, b)$ f_G(a, b) be a boolean function that is true if there exists a path from vertex $1$ to vertex $a$ that traverses exactly $b$ edges (for each $1 \leq a \leq n$ 1 \le a \le n, $0 \leq b$ 0 \le b), and false otherwise. If an edge is traversed multiple times, it is counted that many times in the total.

Elsie wants to copy Bessie. In particular, she wants to construct an undirected graph $G^{'}$ G' such that $f_{G^{'}} (a, b) = f_{G} (a, b)$ f_{G'}(a, b) = f_G(a, b) for all $a$ and $b$ .

Elsie wants to do the least possible amount of work, so she wants to construct the smallest possible graph. Therefore, your task is to compute the minimum possible number of edges in $G^{'}$ G'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1 0^{5}$ 10^5, and the sum of $m$ over all test cases does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Input

The first line contains $t$ ( $1 \leq t \leq 5 \cdot 1 0^{4}$ 1 \le t \le 5 \cdot 10^4), the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ( $2 \leq n \leq 1 0^{5}$ 2 \le n \le 10^5, $n - 1 \leq m \leq \frac{n ^{2} + n}{2}$ n - 1 \le m \le \frac{n^2 + n}{2}).

The next $m$ lines of each test case contain two integers $x$ and $y$ ( $1 \leq x \leq y \leq n$ 1 \le x \le y \le n), denoting an edge between $x$ and $y$ in $G$ .

Consecutive test cases are separated by a blank line for readability.

Output

For each test case, output the minimum possible number of edges in $G^{'}$ G' on a separate line.

Examples

In the first test case, Elsie can construct $G^{'}$ G' by starting with $G$ and removing $(2, 5)$ . Alternatively, she could construct a graph with the following edges, since she is not restricted to just removing edges from $G$ :

Elsie definitely cannot do better than $n - 1$ n - 1 since $G^{'}$ G' must also be connected.

Example 1