한 도시의 경찰서에서 관리하는 순찰 구역들은 덤불로 분리되어 있고, 1부터 N(1≤N≤200)까지 연속적으로 번호가 붙어 있다.

이 도시의 경찰관들은 N개의 순찰지역을 자유롭게 이동하기를 원한다.

경찰관들은 임의의 순찰 구역으로부터 다른 모든 순찰 구역으로 이동할 수 있도록 순찰 구역 쌍들 사이의 샛길들을 관리하기를 원한다.

경찰관들은 그들이 관리하고 있는 샛길을 따라 양방향으로 이동할 수 있다.

경찰관들은 실제로 샛길을 처음부터 새로 만들지 않고,

대신에 그들이 발견한 범죄자들이 만들어 놓은 샛길을 관리함으로써 이동하는데 사용한다.

매주 그들은 이미 발견한 범죄자들이 만든 샛길들의 일부나 전부를 선택하여 관리할 수 있다.

신기하게도 경찰관들은 매주 초에 범죄자들이 만들어 놓은 새로운 샛길을 하나씩 발견한다.

그리고 나서 그들은 임의의 순찰 구역에서 다른 순찰 구역으로 이동할 수 있도록 그 주 동안 관리할 샛길들의 집합을 결정해야 한다.

경찰관들은 현재 그들이 관리하고 있는 샛길들만을 이용할 수 있다.

이와 함께 경찰관들은 항상 그들이 관리해야 하는 샛길의 총 길이를 최소화하기 원한다.

경찰관들이 샛길을 관리하는데 드는 비용은 샛길의 길이에 비례한다.

전번 주에 어떤 샛길을 관리했든지 상관없이,

경찰관은 그들이 이미 발견한 범죄자들의 샛길 집합에 임의의 부분 집합을 선택해서 관리할 수 있다.

범죄자들의 샛길은 결코 직선이 아니다. 같은 두 순찰 구역을 잇는 두 샛길의 길이가 서로 다를 수도 있다.

더구나 두 샛길이 교차하더라고, 경찰들은 지침에 따라, 순찰 구역에서가 아니면 샛길을 바꾸어 이동하지 않는다.

매주 초에 경찰관들은 그들이 새로 발견한 범죄자의 샛길 하나를 알려줄 것이다.

그러면 당신의 프로그램은 경찰관들이 임의의 순찰 구역에서 다른 모든 순찰 구역으로 이동할 수 있도록

그들이 그 주에 관리해야 할 샛길들의 최소 총 길이를 출력해야 한다.

만약 그런 샛길들이 존재하지 않는다면 존재하지 않는다는 표기를 해야 한다.

순찰 구역 관리 timer 1s memory 256MB

순찰 구역 관리 1s 256MB