철도 여행
시간 제한1초메모리 제한512 MB
무방향 그래프가 주어질 때 모든 간선을 정확히 한 번씩 지나는 데 필요한 최소 trail 수를 구한다.
문제
한국에는 N개의 도시 C1, C2, ..., CN가 있고, 두 도시를 양방향으로 잇는 M개의 철도 노선이 있다.
철도를 좋아하는 가희는 철도 여행을 하려고 한다. 철도 여행이란 시작 도시에서 도착 도시까지 철도 노선만을 이용해 이동하는데, 하나의 철도 노선을 두 번 이상 타지 않는 것을 의미한다. 시작 도시와 도착 도시는 같을 수도 있으며, 하나의 도시를 여러 번 방문할 수도 있다.
가희는 최소 횟수의 철도 여행으로 모든 노선을 정확히 한 번씩 타고자 한다. 가희가 철도 여행을 몇 번 해야 하는지 구해보자.
입력
입력의 첫 줄에 두 정수 N(1 ≤ N ≤ 200,000)과 M(1 ≤ M ≤ 300,000)이 주어진다.
이후 M개의 줄에 걸쳐 서로 다른 두 정수 u, v(1 ≤ u, v ≤ N)가 주어진다. 이는 Cu와 Cv를 양방향으로 잇는 철도 노선이 존재함을 의미한다.
단, 두 도시를 직접 잇는 철도 노선은 많아야 하나이다.
출력
가희가 해야 하는 철도 여행의 최소 횟수를 출력한다.