시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 285 104 77 40.957%

문제

한국에는 N개의 도시 C1, C2, ..., CN가 있고, 두 개의 도시를 양방향으로 잇는 M개의 철도 노선이 있다.

철도를 좋아하는 가희는 철도 여행을 하려고 한다. 철도 여행이란 시작 도시에서 도착 도시까지 철도 노선만을 이용해 이동하는데, 하나의 철도 노선을 두 번 이상 타지 않는 것을 의미한다. 시작 도시와 도착 도시는 같을 수도 있으며, 하나의 도시를 여러 번 방문할 수도 있다.

가희는 최소 횟수의 철도 여행으로 모든 노선을 정확히 한 번씩 타고자 한다. 가희가 철도 여행을 몇 번 해야 하는지 구해보자.

입력

입력의 첫 줄에 두 정수 N(1 ≤ N ≤ 200,000)과 M(1 ≤ M ≤ 300,000)이 주어진다.

이후 M개의 줄에 걸쳐 서로 다른 두 정수 u, v(1 ≤ u, v ≤ N)가 주어진다. 이는 CuCv를 양방향으로 잇는 철도 노선이 존재함을 의미한다.

단, 두 개의 도시를 직접 잇는 철도 노선은 많아야 하나이다.

출력

가희가 해야 하는 철도 여행의 최소 횟수를 출력한다.

예제 입력 1

11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3 9
9 10
10 11

예제 출력 1

2

아래 그림의 상황과도 같다. (이미지 출처: 코레일)

KTX 노선 이미지

예제 입력 2

3 3
1 2
2 3
3 1

예제 출력 2

1

예제 입력 3

5 2
1 2
3 4

예제 출력 3

2

1-2, 3-4와 같이 총 두 번의 여행이 필요하다.

예제 입력 4

5 10
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2

예제 출력 4

1

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2019! D번