Connect the GSHS 2

평화롭던 경곽 제국에 위협이 닥쳤다! 바로, 쌀나라의 승원이가 경곽 최고의 먹거리인 쌀을 먹기 위해 침공한 것이다.

이에 경곽 제국의 지배자인 시준이는 총 $K$개의 분열한 왕국들을 다시 합치려고 한다. 현재 $i$번째 왕국은 $1$부터 $N_i$까지 번호가 매겨진 $N_i$개의 마을과, 서로 다른 두 마을을 연결하는 $M_i$개의 다리로 이루어져 있다. 연결하는 마을이 같은 서로 다른 두 다리는 존재하지 않으며, 한 왕국 내의 모든 마을은 다리를 한 번 이상 이용해 서로 오갈 수 있다. 서로 다른 왕국의 마을 사이를 잇는 다리는 존재하지 않는다.

시준이는 각 왕국마다 하나의 마을을 도시로 선택한 후, 이 $K$개의 도시를 선형으로 잇는다. 즉, $K-1$개의 다리로 왕국마다 하나씩 선택된 $K$개의 도시를 모두 잇는데, 각 도시는 최대 $2$개의 다른 왕국의 도시와 연결되도록 한다. 이후 $K$개의 도시 중 한 곳을 수도로 정하려고 한다.

최종적으로, 시준이는 승원이를 막기 위해 수도로 군대를 모으려고 한다. 이를 효율적으로 하기 위해 수도에서 가장 먼 마을까지의 거리를 최소화해야 한다. 여기서 두 마을 사이의 거리는 한 마을에서 다른 마을로 이동할 때 거쳐야 하는 다리 개수의 최솟값으로 정의한다.

시준이를 대신해서 $K$개의 왕국의 도시를 선택하고, $K$개의 도시를 선형으로 이은 뒤, $K$개의 도시 중 수도를 선택하라. 그리고 선택한 수도에서 가장 먼 마을까지의 거리를 출력하라.

첫 번째 줄에 왕국의 수 $K$가 주어진다.

이후 $i = 1, 2, \cdots, K$에 대해 $i$번째 왕국의 정보가 다음과 같이 주어진다:

첫 줄에 마을의 수 $N_i$과 다리의 수 $M_i$이 주어진다.

다음 줄부터 $M_i$개의 줄 중 $j$번째 줄에 다리가 잇는 두 마을의 번호 $s_j, e_j$가 공백으로 구분되어 주어진다.

첫 번째 줄에 문제의 정답을 출력하라.

$1 \leq K \leq 100$ $1 \leq N \leq 500$ $1 \leq M \leq 1000$