간선 추가
시간 제한2초메모리 제한128 MB
그래프에 최소 개수의 간선을 추가해서 연결되어 있고 오일러 경로가 존재하도록 만드는 문제입니다.
문제
무방향 그래프가 주어진다. 여기에 가능한 한 적은 수의 간선을 추가하여, 모든 간선을 한 번씩 지나는 경로가 존재하는 연결 그래프로 만들어야 한다.
모든 간선을 한 번씩 지나는 경로를 오일러 경로라고 한다. 이 경로의 시작 정점과 끝 정점은 같아도 되고 달라도 된다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다.
2 <= V <= 1,000
1 <= E <= V * (V - 1) / 2
정점은 1부터 V까지 번호가 매겨져 있다. 이어지는 E개의 줄에는 간선을 이루는 서로 다른 두 정점 a와 b가 주어진다. 입력으로 주어지는 간선은 모두 서로 다르다.
출력
추가해야 하는 간선 개수의 최솟값을 출력한다.