한 통신 회사가 \(n\) 개의 도시를 연결하기 위해 케이블을 하나씩 설치하고 있다. \(i\) 번째로 설치하는 케이블은 두 도시 \(u\) 와 \(v\) 를 직접 연결한다.

회사는 모든 도시가 (직접 또는 간접적으로) 서로 연결되는 순간이 궁금하다. 즉, 몇 번째 케이블을 설치한 직후 처음으로 전체 네트워크가 하나로 연결되는지를 알고 싶다.

케이블은 주어진 순서대로 설치된다. 모든 케이블을 설치한 후에도 전체가 연결되지 않으면 \(-1\) 을 출력한다.

\(1 \le n \le 120{,}000\), \(1 \le m \le 200{,}000\)

첫째 줄에 도시의 수 \(n\) 과 케이블의 수 \(m\) 이 주어진다. (\(1 \le n \le 120{,}000\), \(1 \le m \le 200{,}000\))

다음 \(m\) 개의 줄에 두 정수 \(u\ v\) 가 설치 순서대로 주어진다. (\(1 \le u, v \le n\)) 같은 두 도시 사이에 케이블이 여러 번 설치될 수도 있고, \(u=v\) 인 경우도 있을 수 있다.

전체 네트워크가 처음으로 연결되는 케이블 번호(1-indexed)를 출력한다. 끝까지 연결되지 않으면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original