Congested Networks

You are given a connected computer network with bidirectional communication. You want to pick two distinct nodes $u$ and $v$ so that the congestion between them — produced by a virus continuously sent back and forth — is as large as possible. The congestion level between $u$ and $v$ is defined as the maximum number of edge-disjoint paths (paths that share no edge) connecting the two nodes.

For example, in the network shown below there are three paths between node 0 and node 6 such that no edge is used by more than one of them. Two paths are allowed to pass through the same node (for instance node 7). No other pair of nodes yields a higher congestion level.

The input is a sequence of connected computer networks. Each network has $n$ nodes labeled ${0, 1, \ldots, n-1}$ with $n \le 40$.

Each network is specified as follows. The first line contains a single non-negative integer $n$, the number of nodes. It is followed by $n$ lines; the $i$-th of these lines lists the neighbors (zero-indexed) of node $i-1$, separated by spaces.

The last network is followed by a network with $n = 0$, which must not be processed. There may be up to 2000 networks.

For each input network, output on its own line a single integer: the maximum congestion level achievable by some pair of nodes in that network.