34016번 - 대도시 구축

문제

당신은 어느 대도시에 교통 시스템을 구축하는 과제를 받았다. 이 대도시는 $N$개의 마을로 구성되어 있고, 각 마을의 번호는 1ドル$부터 $N$까지이다.

이 대도시는 막 완공되어 현재 마을 사이에 어느 도로도 건설되어 있지 않다. 당신은 양방향 도로를 원하는 만큼 건설해 모든 마을 간에 서로 이동이 가능하도록 대도시의 교통 시스템을 구축하려고 한다. 마을 번호가 $a,b$ $(a \neq b)$인 두 마을 사이를 잇는 양방향 도로를 건설하는 데 드는 비용은 $a+b$이다.

한편, 이 대도시에는 $M$개의 강이 있는데, 각 강은 두 마을 사이를 가로질러 흐르고 있다. 이로 인해 각 강을 가로지르는 두 마을 사이에는 양방향 도로를 건설할 수 없다.

당신에게 주어진 예산은 많지 않기 때문에 최소한의 비용으로 모든 마을이 서로 이동 가능하게 만들어야 한다. 최소 건설 비용이 얼마인지 구해보자.

입력

첫째 줄에 대도시를 구성하는 마을 개수 $N$과 두 마을 사이를 가로지르는 강의 개수 $M$이 공백으로 구분되어 주어진다. $(4 \leq N \leq 10^9; 0 \leq M \leq 2)$

둘째 줄부터 $M$개의 줄에 걸쳐 강을 가로지르는 두 마을의 번호 $a, b$가 공백으로 구분되어 주어진다. $(1 \leq a < b \leq N)$

서로 다른 강이 같은 두 마을 사이를 가로지르는 경우는 없다.

출력

첫째 줄에 모든 마을 간에 서로 이동이 가능하도록 양방향 도로들을 건설하는 데 드는 최소 비용을 출력한다.

제한

힌트