미르코와 슬라브코는 크로아티아에서 해마다 열리는 2인승 사이클 장거리 경주의 참가를 앞두고 열심히 기량을 쌓고 있다.

그들은 연습 코스를 설정해 놓고 그 코스대로 꾸준히 주행 연습을 하고 싶어한다.

주변에는 N개의 도시와 M개의 길이 있다. 길은 두 도시를 연결하며 어느 방향으로나 주행이 가능하다.

M개의 길 중 정확하게 N-1개는 포장된 도로이며, 나머지는 비포장 오솔길이다.

단, 모든 도시는 포장도로만으로도 상호 왕래가 가능하게 연결돼 있다.

다시 말해 N개의 도시와 N-1개의 포장도로는 트리 구조를 형성한다는 뜻이다.

아울러, 한 도시를 관통하는 길(포장, 비포장 막론)의 최대 개수는 10개이다.

연습 코스는 한 도시에서 시작해서 임의의 길을 따라 운행한 뒤, 다시 그 도시로 돌아오는 형태이다.

미르코와 슬라브코는 늘 새로운 길을 가는 것을 좋아하기 때문에,

전에 지나쳤던 도시를 또 들르거나 전에 주행했던 도로를 다시 주행하는 일이 없도록 코스를 만들고 싶어 한다.

코스는 아무 도시에서나 시작해도 되며, 모든 도시를 다 거쳐야 할 필요는 없다.

2인승 자전거는 뒤에 타는 게 체력 소모가 더 적다. 앞 사람이 역풍을 가려 주기 때문이다.

그래서 둘은 새로운 도시에 도착할 때마다 자리를 교대한다.

이런 상황에서 두 사람이 서로 동일한 양만치 훈련을 하기 위해서는 연습 코스는 짝수 개의 길을 경유하도록 정해야 한다.

그런데 미르코와 슬라브코를 시샘하는 경쟁자들은,

길의 일부를 폐쇄함으로써 그 두 사람이 위에서 언급한 모든 조건을 만족하는 연습 코스를 전혀 찾을 수 없게 만들기로 작정했다.

비포장 길은 폐쇄하는데 제각기 비용이 들며, 그 비용은 양의 정수로 표현된다.

다만 포장도로는 폐쇄가 불가능하다.

도시와 도로망에 대한 정보를 입력 받아, 위에서 언급한 모든 조건을 만족하는

사이클 연습 코스가 존재하지 않게 만드는데 필요한 최소한의 도로 폐쇄 비용을 계산하는 프로그램을 작성하시오.

사이클코스(Trainings) timer 1s memory 256MB

사이클코스(Trainings) 1s 256MB