서기 4,000년 현재, 지구의 황폐화로 인하여 사람들은 공중에 섬을 띄워 공중도시를 만들어 살아가고 있다.

각 공중도시는 부양무게의 한계로 작은 크기의 섬으로 만들고 대신 다리로 연결하여 모든 도시 사이에 이동이 가능하다.

아래 그림은 도시 1부터 도시 6까지 모두 6개의 공중도시가 서로 다리로 연결된 모습을 보여준다.

두 도시는 서로 다른 두 개 이상의 다리로 직접 연결될 수도 있다.

위 그림에서 도시 2와 도시 4는 서로 다른 두 개의 다리로 연결되어 있다.

그런데, 간혹 발생하는 천재지변 때문에 다리가 끊어질 가능성이 있다.

위 그림에서 도시 5와 도시 6을 잇는 다리가 하나 끊어진다면 도시 6에서는 다른 도시로 이동할 수가 없지만,

도시 1과 도시 3을 잇는 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능하다.

그래서 하나의 다리가 끊어지더라도 여전히 모든 두 도시 사이에 이동이 가능하도록 다리를 추가로 건설하려고 한다.

위 그림의 예에서는 다음 그림과 같이 도시 3과 도시 6을 잇는 다리를 하나 추가로 건설하면 임의의 다리가 하나 끊어지더라도

여전히 모든 도시 사이에 이동이 가능하다.

물론 도시 3 대신 다른 도시와 도시 6을 잇는 다리를 하나 추가해도 가능하다.

공중도시와 현재 상태의 다리가 주어져 있을 때, 임의의 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능할 수 있도록

다리의 길이에 상관없이 추가로 건설해야할 다리의 최소 개수와 그 위치를 찾는 프로그램을 작성하시오.

공중도시 timer 1초 memory 128MB

공중도시 1초 128MB