쾨니히스베르크의 다리

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

요약

주어진 그래프에 간선을 추가해 모든 다리를 지나는 단순 경로가 있도록 할 때, 가능한 다리의 최대 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, DFS, 트리
정답자: 아직 제출이 없습니다

문제

그래프가 주어졌을 때, 그 그래프의 모든 다리(bridge)를 지나는 단순 경로(simple path)가 존재하면 그 그래프를 Königsbergsy라고 한다. 여기서 다리는 제거하면 그래프가 끊어지는 간선이다. 단순 경로는 각 정점을 최대 한 번만 방문하는 경로이다.

그래프 $G$ 가 주어진다. $G$ 에 간선을 몇 개 추가하여 Königsbergsy한 그래프로 만들고자 한다. 같은 두 정점 사이에 간선을 여러 개 추가해도 된다. 결과 그래프가 가질 수 있는 다리의 최대 개수를 구하라.

입력

첫째 줄에 정점의 개수 $n$ 과 간선의 개수 $m$ 이 주어진다 ( $2 \leq n \leq 10^6$ ; $0 \leq m \leq 10^6$ ).

이후 $m$ 개의 줄에 각각 간선 하나를 나타내는 두 정수 $u_i$ , $v_i$ ( $0 \leq u_i, v_i \leq n-1$ )가 주어진다. 이는 정점 $u_i$ 와 $v_i$ 사이의 간선이다.

출력

결과 그래프가 가질 수 있는 다리의 최대 개수를 정수 하나로 출력한다.

예제2

예제 1
입력
```
4 3
0 1
1 2
2 0
```
예상 출력
```
1
```
예제 2
입력
```
4 2
0 1
1 2
```
예상 출력
```
3
```