평화롭던 경곽 제국에 위협이 닥쳤다! 바로, 쌀나라의 승원이가 경곽 최고의 먹거리인 쌀을 먹기 위해 침공한 것이다.
이에 경곽 제국의 지배자인 시준이는 총 개의 분열한 왕국들을 다시 합치려고 한다. 현재 번째 왕국은 부터 까지 번호가 매겨진 개의 마을과, 서로 다른 두 마을을 연결하는 개의 다리로 이루어져 있다. 연결하는 마을이 같은 서로 다른 두 다리는 존재하지 않으며, 한 왕국 내의 모든 마을은 다리를 한 번 이상 이용해 서로 오갈 수 있다. 서로 다른 왕국의 마을 사이를 잇는 다리는 존재하지 않는다.
시준이는 각 왕국마다 하나의 마을을 도시로 선택한 후, 이 개의 도시를 선형으로 잇는다. 즉, 개의 다리로 왕국마다 하나씩 선택된 개의 도시를 모두 잇는데, 각 도시는 최대 개의 다른 왕국의 도시와 연결되도록 한다. 이후 개의 도시 중 한 곳을 수도로 정하려고 한다.
최종적으로, 시준이는 승원이를 막기 위해 수도로 군대를 모으려고 한다. 이를 효율적으로 하기 위해 수도에서 가장 먼 마을까지의 거리를 최소화해야 한다. 여기서 두 마을 사이의 거리는 한 마을에서 다른 마을로 이동할 때 거쳐야 하는 다리 개수의 최솟값으로 정의한다.
시준이를 대신해서 개의 왕국의 도시를 선택하고, 개의 도시를 선형으로 이은 뒤, 개의 도시 중 수도를 선택하라. 그리고 선택한 수도에서 가장 먼 마을까지의 거리를 출력하라.
첫 번째 줄에 왕국의 수 가 주어진다.
이후 에 대해 번째 왕국의 정보가 다음과 같이 주어진다:
첫 줄에 마을의 수 과 다리의 수 이 주어진다.
첫 번째 줄에 문제의 정답을 출력하라.
다음 줄부터 개의 줄 중 번째 줄에 다리가 잇는 두 마을의 번호 가 공백으로 구분되어 주어진다.
| 3 | 15 |
| 4 | 40 | 추가적인 제약 조건 없음. |
