문제

현대모비스는 차량의 성능을 실험하기 위해 여러 테스트를 할 수 있는 주행시험장을 갖추고 있다. 주행시험장은 번부터 번까지 번호가 매겨진 개의 차량 정비소와 개의 주행 구간으로 구성되어 있다. 주행 구간은 정비소와 정비소를 양방향으로 이어주며, 시작과 끝이 같은 정비소일 수 있다. 

주행테스트 대상 차량은 번 정비소에서 출발하여 모든 주행 구간을 한 번씩 통과한 뒤 번 정비소로 돌아와야 하고, 번 정비소에서 테스트의 통과 여부가 결정된다.

최근 성능을 시험할 차의 종류가 늘어나 기존의 주행테스트 시설로는 모든 차종의 주행테스트가 불가능하게 되었다. 이에 폐쇄되었던 시설을 활용하여 주행테스트를 하고자 한다. 폐쇄되었던 주행시험장은  현재와 다른 테스트 방법 때문에 번 정비소에서 출발하여 모든 주행 구간을 한 번씩 통과한 뒤 다시 번 정비소로 돌아올 수 있는지 알 수 없는 상황이다. 만약 가능하다면 시설을 그대로 사용하고, 불가능하면 최소 개수의 주행 구간을 추가하여 시설을 사용하고자 한다.

주행 테스트 시설의 정보가 주어졌을 때, 조건을 만족하기 위해 추가해야 하는 최소 주행 구간의 개수를 구하시오.

입력

첫 번째 줄에는 주행시험장 내의 정비소의 개수 과 주행 구간의 개수 이 공백으로 구분되어 주어진다.

두 번째 줄부터 개의 줄에 걸쳐 주행 구간이 의 형태로 한 줄에 하나씩 주어진다. 이는 두 정비소 , 를 이어주는 주행 구간이 있음을 뜻하며 번 정비소에서 번 정비소 또는 번 정비소에서 번 정비소로 이동 가능하다. 

출력

번 정비소에서 출발하여 모든 주행 구간을 한 번씩 통과한 뒤 번 정비소로 돌아오기 위해 추가해야 하는 주행 구간의 최소 개수를 출력한다.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!