1178번 - 간선 추가

문제

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

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

입력

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

출력

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

제한

힌트