Message Broadcasting

The internet-based company ACM (Analog Computing Machinery) has built a network of people to broadcast an emergency message created by its chief executive officer (CEO) to every employee. The network is a rooted tree: each employee corresponds to one node of the tree, and the CEO corresponds to the root node. Initially only the CEO, the root node, knows the emergency message.

In a single round (one unit of time), any node that already knows the message may forward it to at most one of its children. We want the minimum number of rounds needed for the message to reach every employee.

For example, when the tree looks like Figure 1, the minimum number of rounds is 5. Each directed edge in Figure 1 shows one employee forwarding the message to another, and every node marked with a dot is an employee who has already received the emergency message (including the CEO).

Figure 1. An emergency message from the root node broadcast through a rooted tree in five rounds.

Given a rooted tree, write a program that computes the minimum number of rounds required for the emergency message from the root node to reach all nodes.

Your program reads from standard input. The input consists of $T$ test cases. The first line contains the number of test cases $T$.

The first line of each test case contains an integer $n$ ($1 \le n \le 5000$), the number of nodes in the rooted tree. Nodes are numbered from $1$ to $n$, and node $1$ is the root.

Each of the next $n$ lines describes the children of one node and contains at least two integers $m\ k\ c_1\ c_2\ \dots\ c_k$ ($1 \le m \le n$, $0 \le k \le n$), where $m$ is a node of the tree, $k$ is the number of children of node $m$, and $c_1\ c_2\ \dots\ c_k$ are the $k$ children of node $m$.

Your program writes to standard output. Print exactly one line for each test case, containing the minimum number of rounds required to broadcast the emergency message from the root node to all nodes.