30680번 - 별자리 만들기

문제

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

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

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

별자리를 만들기 전에 스타는 다음과 같은 용어들을 정의했다.

• 별자리에서 별을 하나 선택하고 무지갯빛 별부터 선택한 별까지 실을 따라 이동할 때, 거치는 실의 최소 갯수를 해당 별의 깊이라고 정의한다.
• 별자리의 모든 별의 깊이를 구해서 이 중 최댓값을 별자리의 길이로 정의한다.

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

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

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

입력

첫째 줄에 장식의 개수 $N$이 정수로 주어진다. $(1 \leq N \leq 100 ,円 000)$

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

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

장식을 구성하는 별의 총개수는 500ドル ,円 000$개를 넘지 않는다.

출력

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

제한

힌트