새 학기를 맞아 한 대학에 \(N\) 개의 신입생 동아리가 만들어졌다. 동아리에는 \(1\) 번부터 \(N\) 번까지 번호가 붙어 있으며, 처음에는 모두 서로 다른 독립된 동아리이다.

시간이 흐르면서 총 \(M\) 건의 합병 신청이 시간 순서대로 접수된다. \(i\) 번째 신청은 두 동아리 번호 \(a\), \(b\) 로 이루어지며, 두 동아리를 하나로 합쳐 달라는 요청이다. 합병이 거듭되면 여러 동아리가 하나의 동아리로 묶일 수 있다.

어떤 신청이 접수되었을 때, \(a\) 가 속한 동아리와 \(b\) 가 속한 동아리가 서로 다른 동아리라면 두 동아리가 실제로 합쳐지므로 이 신청을 유효 합병이라고 부른다. 반대로 \(a\) 와 \(b\) 가 (그동안의 합병으로) 이미 같은 동아리에 속해 있다면 합병이 일어나지 않으므로 이 신청은 무시된다. (같은 동아리를 가리키는 \(a = b\) 인 신청도 무시된다.)

\(M\) 건의 신청을 순서대로 처리할 때, 그중 유효 합병이 몇 번 일어나는지 세는 프로그램을 작성하라.

\(1 \le N \le 200{,}000\)

\(0 \le M \le 500{,}000\)

\(1 \le a, b \le N\)

첫째 줄에 동아리의 수 \(N\) 과 합병 신청의 수 \(M\) 이 공백으로 구분되어 주어진다 (\(1 \le N \le 200{,}000\), \(0 \le M \le 500{,}000\)).

이어지는 \(M\) 개의 줄에는 각각 두 정수 \(a\), \(b\) (\(1 \le a, b \le N\)) 가 주어지며, 이는 시간 순서대로 접수된 합병 신청을 의미한다.

\(M\) 건의 신청 중 유효 합병이 일어난 횟수를 한 줄에 출력한다.

riseoj 작성

출처 Original