빠진 다리
면접 대비시간 제한2초메모리 제한512 MB
모든 다리를 한 번씩 건너 출발한 섬으로 돌아오는 경로가 생기도록 새로 놓을 다리의 최소 개수와 그 다리들을 구합니다.
문제
그림 1은 1부터 4까지 번호가 붙은 점으로 표시된 4개의 섬과, 선으로 표시된 7개의 다리를 보여준다. 각 다리는 서로 다른 두 점을 잇고, 양방향으로 건널 수 있다. 모든 다리 순회(all-bridges-walk)는 어떤 섬에서 출발해 모든 다리를 정확히 한 번씩 건너고 출발한 섬으로 돌아오는 경로다.
그림 1의 섬과 다리로는 이런 순회를 할 수 없다. 하지만 새 다리를 지으면 가능해진다. 예를 들어 4번 섬과 1번 섬을 잇는 다리, 2번 섬과 3번 섬을 잇는 다리를 새로 지으면 순회할 수 있다. 그림 2는 4개의 섬과 3개의 다리가 있는 지역을 보여준다. 이 지역에서는 3번 섬과 4번 섬을 잇는 다리 두 개를 추가하면 순회에 충분하다.
나라에 N개의 섬과 M개의 다리가 있다. 이 나라에서 모든 다리 순회가 가능하도록 새로 지어야 하는 다리의 최소 개수를 구하는 프로그램 bridges를 작성하라.
입력
첫 줄에 정수 과 이 주어진다. 이고 이다. 이어지는 개의 줄에는 다리 한 개의 양 끝에 있는 섬 번호가 주어진다.
출력
첫 줄에 새로 지어야 하는 다리의 개수 를 출력한다. 이어지는 개의 줄에는 새 다리 한 개의 양 끝 섬 번호를 출력한다. 모든 다리 순회를 보장하는 새 다리의 집합이라면 어떤 집합이든 정답으로 인정한다. 새 다리가 필요 없으면 0만 출력한다.