스키어

어느 산의 남쪽 사면에는 여러 개의 스키 코스와 리프트 한 대가 있습니다. 모든 코스는 리프트의 정상 승강장에서 아래쪽 승강장까지 내려갑니다. 매일 아침 리프트 작업자들이 코스 상태를 점검합니다. 이들은 함께 리프트를 타고 정상 승강장까지 올라간 뒤, 각자 원하는 코스를 골라 아래쪽 승강장까지 내려갑니다. 각 작업자는 정확히 한 번만 내려갑니다. 서로 다른 작업자의 경로는 일부 구간이 겹칠 수 있습니다. 모든 경로는 항상 아래쪽으로만 이어집니다.

스키장은 숲속의 오솔길(연결로)로 이어진 빈터들의 연결망입니다. 각 빈터의 높이는 모두 다르며, 임의의 두 빈터를 직접 잇는 연결로는 많아야 하나입니다. 정상에서 아래쪽으로 내려가는 동안 작업자는 어떤 빈터든 지날 수 있습니다(다만 한 번의 활강으로 모든 빈터를 지날 수 있는 것은 아닙니다). 경로는 오직 빈터에서만 만나며, 터널이나 다리는 없습니다.

어떤 연결로는 적어도 한 명의 작업자가 그 위를 지나가면 점검된 것으로 봅니다. 작업자들은 되도록 적은 인원으로 빈터 사이의 모든 연결로를 점검하려고 합니다.

스키 코스 지도를 입력받아, 모든 작업자의 경로가 합쳐서 모든 연결로를 덮기 위해 필요한 작업자의 최소 인원을 구하는 프로그램을 작성하세요.

첫째 줄에 빈터의 수를 나타내는 정수 $n$이 주어집니다($2 \le n \le 5000$). 빈터는 $1$번부터 $n$번까지 번호가 매겨져 있으며, $1$번 빈터가 리프트의 정상 승강장, $n$번 빈터가 아래쪽 승강장입니다.

이어지는 $n-1$개의 줄은 각 빈터에서 아래로 내려가는 연결로를 나타냅니다. $i+1$번째 줄($i$는 $1$부터 $n-1$까지)은 $i$번 빈터를 설명하며, 먼저 $i$번 빈터에서 아래로 내려가는 연결로의 개수 $k$가 주어지고, 이어서 그 연결로들이 이어지는 $k$개의 빈터 번호가 연결로의 배치 순서에 따라 서쪽에서 동쪽 방향으로 주어집니다.

숲속의 모든 연결로를 점검할 수 있는 작업자의 최소 인원을 정수 하나로 출력합니다.