문제
정올국은 여러개의 도시로 이뤄진 나라이며, 한 도시에서 다른 도시로 가기 위해서는 반드시 연결된 도로를 이용하여 이동해야 한다.
만약 도시 A와 도시 B에 도로가 있을 경우 도시 A와 도시 B로 이동이 가능하며, 역으로 도시 B에서 도시 A로 이동할 수 있다. 두개의 도시간에 여러개의 도로가 연결 될 수도 있다.
최근 정올국은 폭우로 인해 도시와 도시 사이를 연결하는 도로가 다수 파손이 되어 이를 복원하고자 한다.
원래 정올국의 도로망은 특정 도시에서 시작해서 모든 도로를 정확히 한번씩만 거처서 갈 수 있는 특징을 가지고 있다. 단 여기서 마지막에 도착하게 되는 도시는 이동을 시작한 도시일 필요는 없다.
원래의 도로망의 특징을 살리기 위해서 임의의 도시들 사이에 도로를 잇고자 할 때, 비용을 줄이기 위해 건설해야하는 최소 도로의 수를 출력하는 프로그램을 작성하라.
입력
입력의 첫 행에는 두 정수 V, E가 주어진다. V는 도시의 수로 100이하이고, E는 도로의 수로 10,000이하이다.
다음 E 개의 행에 걸쳐 도로에 연결된 도시의 번호가 공백으로 구분되어 주어진다. 도시의 번호는 0부터 센다.
출력
입력에 대해 건설해야 하는 최소 도로의 수를 출력한다.
예제
4 3
0 1
1 2
1 3
1
로그인해야 코드를 작성할 수 있어요.