Connectedness

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

Draw the edges one by one, in the order they are given. Find how many edges you have drawn when the graph first becomes connected.

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

A graph is connected if, for 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$ also lets you travel from $v$ to $u$.

The first line 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.

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

Print the number of edges drawn the first time the graph becomes connected, or -1 if it never does.