메시지 전파

인터넷 기반 기업 ACM(Analog Computing Machinery)은 최고경영자(CEO)가 만든 긴급 메시지를 모든 직원에게 전달하기 위해 사람들로 이루어진 네트워크를 구성했다. 이 네트워크는 루트가 있는 트리 구조이며, 각 직원은 트리의 한 노드에, CEO는 루트 노드에 대응한다. 처음에는 루트 노드인 CEO만 긴급 메시지를 알고 있다.

한 번의 라운드(단위 시간) 동안, 메시지를 알고 있는 노드는 자신의 자식 노드 가운데 최대 한 명에게만 메시지를 전달할 수 있다. 이때 메시지가 모든 직원에게 전달되기까지 필요한 최소 라운드 수를 구하려고 한다.

예를 들어 트리가 그림 1과 같을 때 최소 라운드 수는 5이다. 그림 1의 각 방향 간선은 한 직원이 다른 직원에게 메시지를 전달하는 것을 나타내며, · 로 표시된 노드는 (CEO 자신을 포함하여) 이미 긴급 메시지를 받은 직원을 뜻한다.

그림 1. 루트 노드의 긴급 메시지가 트리를 따라 5 라운드 만에 전파되는 모습.

루트가 있는 트리 구조가 주어질 때, 루트 노드의 긴급 메시지가 모든 노드에 전달되기까지 필요한 최소 라운드 수를 구하는 프로그램을 작성하라.

입력은 표준 입력으로 주어진다. 입력은 $T$개의 테스트 케이스로 이루어지며, 첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 트리의 노드 수 $n$ ($1 \le n \le 5000$)이 주어진다. 각 노드는 $1$부터 $n$까지 번호가 매겨지며, 루트 노드의 번호는 $1$이다.

이어지는 $n$개의 줄에는 각 노드의 자식 목록이 주어진다. 각 줄은 $m\ k\ c_1\ c_2\ \dots\ c_k$ 형태로 적어도 두 개의 정수를 포함한다 ($1 \le m \le n$, $0 \le k \le n$). 여기서 $m$은 트리의 한 노드, $k$는 노드 $m$의 자식 수, $c_1\ c_2\ \dots\ c_k$는 노드 $m$의 $k$개 자식이다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 정확히 한 줄을 출력하며, 그 줄에는 루트 노드에서 모든 노드로 긴급 메시지를 전파하는 데 필요한 최소 라운드 수를 적는다.