분재

많은 사람은 분재를 기르는 것을 좋아하는데, 그것이 "svårt"하고 "harmoniskt"하다고 말하기 때문이다. Torstina가 분재를 기르는 이유는 그것이 아니다. 그녀는 그저 분재를 팔아 많은 돈을 벌고, 그 돈으로 많은 체리모야를 사고 싶을 뿐이다. 그녀는 방금 새 혹을 심었고 체리모야가 몹시 먹고 싶다. 그래서 고객이 원하는 분재가 생길 때까지 몇 년을 기다려야 하는지 궁금해한다.

분재에는 $N$개의 혹과 $N-1$개의 가지가 있다. 혹에는 0부터 $N-1$까지 번호가 매겨져 있다. 모든 분재는 땅에 심는 작은 혹 하나에서 시작한다. 매년 각 혹에서 새 가지 하나가 자라며, 그 끝에는 새 혹이 생긴다. 또한 언제든지 나무에서 가지를 잘라낼 수 있다. 나무에서 뿌리가 어디에 있는지는 중요하지 않다는 점에 유의하라.

고객이 원하는 분재가 주어질 때, Torstina가 정확히 똑같은 나무를 기를 때까지 몇 년을 기다려야 하는가?

점수

여러 테스트 케이스 그룹으로 해답을 평가한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$9$| $m_i\leq 2$, 정점 0에서 나무를 기르기 시작하는 것이 가장 좋다.

$2$ |$11$| $m_i \leq 3$, 정점 0에서 나무를 기르기 시작하는 것이 가장 좋다.

$3$ |$18$| $A \leq 15$, 정점 0에서 나무를 기르기 시작하는 것이 가장 좋다.

$4$ |$22$| 정점 0에서 나무를 기르기 시작하는 것이 가장 좋다.

$5$ |$12$| $N \leq 250$.

$6$ |$28$| 추가 제한이 없다.

첫째 줄에 고객의 분재에 있는 혹의 수를 나타내는 정수 $N$ ($2 \leq N \leq 10^5$)이 주어진다. 이어지는 $N$개의 줄에는 분재가 다음과 같이 설명된다. $i$번째 줄에는 먼저 혹 $i$에서 뻗어 나가는 가지의 수를 나타내는 정수 $0 < m_i < N$이 주어진다. 그다음에는 혹 $i$와 연결된 혹들을 나타내는 $m_i$개의 정수가 주어진다.

Torstina가 고객이 원하는 분재를 기르는 데 걸리는 연수를 나타내는 정수 $A$을 출력한다.

아래 그림과 같이 자라게 하면 2년 만에 나무를 기를 수 있다.

첫 번째 예제의 분재를 두 해 만에 기를 수 있는 두 가지 방법 중 하나.