그래프 연결하기

정점 $N$개와 간선 $M$개로 이루어진 무향 그래프가 주어진다. 정점에는 $1,2,\cdots,N$의 번호가 붙어 있다.

두 정점 $u,v$가 연결되어 있다는 것은, $u$에서 시작하여 간선을 따라 이동하는 것을 $0$번 이상 반복해 $v$에 도달할 수 있다는 뜻이다. 특히 모든 정점은 자기 자신과 연결되어 있다.

그래프에 새로운 무향 간선을 몇 개 추가하여, 모든 정점 쌍이 연결되어 있도록 만들고자 한다. 추가해야 하는 간선 개수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$

이는 각 $i$ ($1 \leq i \leq M$)에 대해 $u_i$와 $v_i$를 잇는 무향 간선이 존재함을 의미한다.

첫째 줄에 추가해야 하는 간선 개수의 최솟값을 출력한다.

• $1 \leq N \leq 200\ 000$.
• $0 \leq M \leq \min\left(\frac{N(N-1)}{2}, 300\ 000\right)$.
• $1 \leq u_i,v_i \leq N$ ($1 \leq i \leq M$).
• $u_i \neq v_i$ ($1 \leq i \leq M$).
• $(u_i,v_i)$와 $(v_i,u_i)$를 같은 간선으로 보았을 때, 입력에 같은 간선이 두 번 이상 주어지지 않는다.