시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 164 5 5 5.682%

문제

그래프에 최소 개수의 간선을 추가해서 한붓그리기가 가능한 연결 그래프로 만드는 프로그램을 작성하시오.

한붓그리기가 가능하다는 것은 한 번 지난 간선을 다시 지나지 않으면서 모든 간선을 지나는 경로가 존재한다는 것을 의미한다. 시작점과 끝점은 같을 수도 있고 다를 수도 있다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (2≤V≤1,000, 1≤E≤V×(V-1)÷2) 정점에는 1부터 V까지 번호가 매겨져 있다고 생각한다. 이어서 E개의 줄에 걸쳐 간선을 이루는 두 점 a와 b가 주어진다. a와 b는 서로 다르며, 입력으로 주어지는 모든 간선 역시 서로 다르다.

출력

첫째 줄에 추가해야 하는 간선 개수의 최소값을 출력한다.

예제 입력

5 3
1 2
1 3
4 5

예제 출력

1

힌트

출처