Wooksin-ness of a graph

Problem

At the headquarters of algospot.com, Toivoa "the chairman" kept pestering Astein "the slave" for a new graph problem for a long time. So Astein came up with the following problem.

The Wooksin-ness of an undirected graph $G(V, E)$ is the minimum number of additional edges needed for the graph to contain a cycle. Formally:

$\min |E' - E| \quad \text{s.t.} \quad E' \supseteq E \text{ and } G'(V, E') \text{ has at least one cycle}$

Loops (edges that start and end at the same vertex) and multiple edges between the same pair of vertices are not allowed.

Write a program that calculates the Wooksin-ness of a given graph.

Input

The input consists of $T$ test cases. The first line contains the number of test cases $T$.

The first line of each test case contains two integers $V$ and $E$ ($1 \le V \le 100$, $0 \le E \le 1000$), where $V$ is the number of vertices and $E$ is the number of edges. The vertices are numbered from $0$ to $V - 1$. Each of the following $E$ lines contains two integers, the numbers of the two vertices joined by an edge.

The input contains no loops. There is at most one edge between any pair of vertices.

Output

For each test case, print one line containing the minimum number of edges that must be added to the graph so that it contains a cycle. If this is impossible, print $-1$.