Problem E
Connectedness

You are given an undirected graph $G=(V,E)$.

If you are drawing in the edges one by one, how many edges did you add when the graph becomes connected for the first time.

If the graph never becomes connected after drawing all the edges, output -1.

Here are some useful definitions:

• A graph is connected if between any two vertices $u,v \in V$, you can reach $u$ from $v$ along a path of edges.

• A graph is undirected if every edge from a vertex $u$ to a vertex $v$ allows travel from vertex $v$ to vertex $u$ as well.

Input

The input line of input contains two space-separated integers $N$ $(1 \leq N \leq 10^6)$ and $M$ $(0 \leq M \leq \min (10^6, \binom {N}{2}))$, the number of vertices and edges in the graph.

Each of the remaining $M$ lines contains two space-separated integers $u_i$ and $v_i$ $(1 \leq u_i, v_i \leq N)$, denoting an undirected edge from node $u_i$ to node $v_i$. No edge connects a node to itself, and there is at most one edge between any pair of nodes.

Output

Print either the number of edges that you added the first time graph becomes connected and -1 otherwise.

2 0

-1

1 0

0

7 11
1 4
1 5
1 6
1 7
2 3
3 4
3 5
3 6
4 7
5 6
6 7

6