별자리 만들기

밤하늘에 무지갯빛 별이 하나 반짝이고 있다. 스타는 이 무지갯빛 별과 $N$개의 장식을 사용해서 별자리를 만들어 밤하늘을 예쁘게 꾸미려고 한다.

각 장식의 특징은 다음과 같다.

• 각 장식은 $A_i$개의 별과 $(A_i-1)$개의 실로 이루어진 트리다. 실은 서로 다른 두 별을 연결한다.
• 각 장식에는 정확히 $1$개의 붉은색 별이 있다. 붉은색 별을 루트 노드로 생각했을 때, 리프 노드에 해당하는 별들은 전부 파란색이다. 나머지 별들은 전부 흰색이다.
• 각 별에는 번호가 적혀 있다. 번호는 $1$ 이상 $A_i$ 이하의 정수이다. 붉은색 별의 번호는 항상 $1$번이며, 별마다 서로 다른 번호가 적혀 있다.

별자리에서 별을 하나 선택하고, 무지갯빛 별에서 선택한 별까지 실을 따라 이동할 때 거치는 실의 최소 개수를 그 별의 깊이라고 정의한다.

별자리의 모든 별의 깊이를 구해 그중 최댓값을 별자리의 길이로 정의한다.

스타는 장식을 한 개씩 받아 가며 별자리에 단다. 모든 장식은 받은 순서대로 다음 규칙을 지키면서 달아야 한다.

• 첫 번째 장식의 붉은색 별과 무지갯빛 별을 실로 연결한다.
• $i$번째 장식($i > 1$)의 붉은색 별은, 앞의 $i-1$개 장식으로 만든 별자리에서 아직 다른 장식과 연결되지 않은 파란색 별 중 깊이가 최소인 별과 실로 연결한다. 이런 별이 여러 개라면 그중 아무거나 고른다.

스타는 규칙을 지키면서 길이가 최소인 별자리를 만들고 싶어 한다. 스타가 만들 수 있는 별자리 길이의 최솟값을 구하라.

첫째 줄에 장식의 개수 $N$이 정수로 주어진다. ($1 \le N \le 100000$)

둘째 줄부터는 스타가 받는 순서대로 $N$개의 장식에 대한 정보가 주어진다.

각 장식에 대해 첫째 줄에는 별의 개수 $A_i$가 정수로 주어진다. 둘째 줄부터 $A_i-1$개의 줄에는 실로 연결된 두 별의 번호 $v$와 $w$가 공백을 사이에 두고 주어진다. ($2 \le A_i \le 100000$; $1 \le v, w \le A_i$; $v \ne w$)

장식을 구성하는 별의 총개수는 500000개를 넘지 않는다.

스타가 만들 수 있는 별자리 길이의 최솟값을 출력한다.