대도시 구축

시간 제한1초메모리 제한512 MB

요약

두 마을을 잇는 도로 비용이 a+b일 때, 최대 두 쌍의 건설 금지 구간이 주어진 상황에서 N개 마을을 모두 연결하는 최소 비용을 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 최소 신장 트리, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

당신은 어느 대도시에 교통 시스템을 구축하는 과제를 받았다. 이 대도시는 $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)$

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

출력

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

예제2

예제 1
입력
```
4 2
1 2
2 4
```
예상 출력
```
14
```
예제 2
입력
```
4 0
```
예상 출력
```
12
```