시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 698 | 276 | 217 | 41.491% |
한국에는 N개의 도시 C1, C2, ..., CN가 있고, 두 개의 도시를 양방향으로 잇는 M개의 철도 노선이 있다.
철도를 좋아하는 가희는 철도 여행을 하려고 한다. 철도 여행이란 시작 도시에서 도착 도시까지 철도 노선만을 이용해 이동하는데, 하나의 철도 노선을 두 번 이상 타지 않는 것을 의미한다. 시작 도시와 도착 도시는 같을 수도 있으며, 하나의 도시를 여러 번 방문할 수도 있다.
가희는 최소 횟수의 철도 여행으로 모든 노선을 정확히 한 번씩 타고자 한다. 가희가 철도 여행을 몇 번 해야 하는지 구해보자.
입력의 첫 줄에 두 정수 N(1 ≤ N ≤ 200,000)과 M(1 ≤ M ≤ 300,000)이 주어진다.
이후 M개의 줄에 걸쳐 서로 다른 두 정수 u, v(1 ≤ u, v ≤ N)가 주어진다. 이는 Cu와 Cv를 양방향으로 잇는 철도 노선이 존재함을 의미한다.
단, 두 개의 도시를 직접 잇는 철도 노선은 많아야 하나이다.
가희가 해야 하는 철도 여행의 최소 횟수를 출력한다.
11 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 3 9 9 10 10 11
2
아래 그림의 상황과도 같다. (이미지 출처: 코레일)
3 3 1 2 2 3 3 1
1
5 2 1 2 3 4
2
1-2, 3-4와 같이 총 두 번의 여행이 필요하다.
5 10 1 2 2 3 3 4 4 5 5 1 1 3 2 4 3 5 4 1 5 2
1
Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2019! D번