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

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

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

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

그런데, 간혹 발생하는 천재지변 때문에 다리가 끊어질 가능성이 있다. 위 그림에서 도시 5와 도시 6을 잇는 다리가 하나 끊어진다면 도시 6에서 는 다른 도시로 이동할 수가 없지만, 도시 1과 도시 3을 잇는 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능하다.

그래서 하나의 다리가 끊어지더라도 여전히 모든 두 도시 사이에 이동이 가능하도록 다리를 추가로 건설하려고 한다. 위 그림의 예에서는 다음 그림 과 같이 도시 3과 도시 6을 잇는 다리를 하나 추가로 건설하면 임의의 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능하다. 물론 도시 3 대신 다른 도시와 도시 6을 잇는 다리를 하나 추가해도 가능하다.

공중도시와 현재 상태의 다리가 주어져 있을 때, 임의의 다리가 하나 끊어지더라도 여전히 모든 도시 사이에 이동이 가능할 수 있도록 다리의 길이에 상관없이 추가로 건설해야할 다리의 최소 개수와 그 위치를 찾는 프로그램을 작성하시오.