혼잡한 네트워크

양방향 통신이 가능한 연결된 컴퓨터 네트워크가 주어진다. 서로 다른 두 노드 $u$와 $v$를 골라, 이 둘 사이로 바이러스를 끊임없이 주고받을 때의 혼잡도(congestion)를 최대로 만들고자 한다. 두 노드 $u$와 $v$ 사이의 혼잡도는, 두 노드를 잇는 서로소 간선 경로(edge-disjoint path, 서로 겹치는 간선이 없는 경로)의 최대 개수로 정의한다.

예를 들어 아래 그림의 네트워크에서는 노드 0과 노드 6 사이에, 사용하는 간선이 서로 겹치지 않는 세 개의 경로가 존재한다. 서로 다른 두 경로가 같은 노드(예: 노드 7)를 함께 지나는 것은 허용된다. 다른 어떤 노드 쌍도 이보다 더 높은 혼잡도를 만들 수 없다.

입력은 각각 $n$개의 노드를 가진, 연결된 컴퓨터 네트워크들의 수열이다. 노드는 ${0, 1, \ldots, n-1}$로 번호가 매겨지며 $n \le 40$이다.

각 네트워크의 명세는 다음과 같다. 첫 줄에는 노드의 개수를 나타내는 음이 아닌 정수 $n$이 주어진다. 이어서 $n$개의 줄이 주어지며, 그중 $i$번째 줄에는 노드 $i-1$의 이웃(0부터 시작하는 번호)들이 공백으로 구분되어 나열된다.

마지막 네트워크 다음에는 $n = 0$인 네트워크가 주어지며, 이 네트워크는 처리하지 않는다. 네트워크는 최대 2000개까지 주어질 수 있다.

각 입력 네트워크에 대해, 그 네트워크에서 어떤 노드 쌍이 만들 수 있는 최대 혼잡도를 정수 하나로 한 줄에 출력한다.