연결성

무방향 그래프 $G=(V,E)$가 주어진다.

간선을 주어진 순서대로 하나씩 그린다. 그래프가 처음으로 연결되는 시점까지 그린 간선의 개수를 구하라.

모든 간선을 그린 뒤에도 그래프가 연결되지 않으면 -1을 출력한다.

그래프가 연결되어 있다는 것은, 임의의 두 정점 $u,v \in V$에 대해 간선을 따라 $v$에서 $u$로 갈 수 있다는 뜻이다.

그래프가 무방향이라는 것은, 정점 $u$에서 정점 $v$로 가는 간선이 $v$에서 $u$로 가는 이동도 허용한다는 뜻이다.

첫 줄에 정점의 수 $N$ $(1 \leq N \leq 10^6)$과 간선의 수 $M$ $(0 \leq M \leq \min(10^6, \binom{N}{2}))$이 공백으로 구분되어 주어진다.

이후 $M$개의 줄에는 각각 무방향 간선의 양 끝점 $u_i$와 $v_i$ $(1 \leq u_i, v_i \leq N)$가 공백으로 구분되어 주어진다. 자기 자신을 잇는 간선은 없으며, 같은 두 정점을 잇는 간선은 최대 한 개이다.

그래프가 처음으로 연결되었을 때 그린 간선의 개수를 출력한다. 연결되지 않으면 -1을 출력한다.