18123번 - 평행우주

서강 프로그래밍 대회가 열리고 있는 지금도 수많은 별들이 다산관의 하늘을 수놓고 있다.

태한이는 컴퓨터공학과지만, 취미로 별을 연구하고 있다. 이미 평행우주가 존재한다는 것을 증명하는 데 성공한 태한이는 별 연구에 너무 심취한 나머지 모든 평행우주의 모든 별들을 별자리로 만들었다.

별자리는 별 n개와 별을 잇는 선 n − 1개로 정의되며, 한 별자리에 속한 모든 별들은 연결되어 있다. 태한이는 별자리를 정의할 때 한 평행우주에 같은 위상의 별자리가 있을 수 없도록 정의했다. 한 별자리의 별들의 연결 관계를 바꾸지 않고 위치만을 움직여서 다른 별자리를 만들 수 있다면 두 별자리의 위상이 같다고 말한다.

한편 한나는 우리가 살고 있는 평행우주에 존재하는 모든 별자리를 찍기 위해, 태한이에게서 별자리들의 정보가 담긴 연구 노트를 받았다. 태한이의 연구 노트에는 모든 평행우주의 모든 별자리에 대한 정보가 적혀 있었지만, 안타깝게도 각각의 별자리가 어떤 평행우주에 있는지는 적혀 있지 않았다.

태한이의 연구 노트를 토대로 한나가 찍을 사진의 최대 장 수를 계산해 주자. 한나는 별자리 하나당 한 장의 사진을 찍는다.

첫 번째 줄에는 모든 평행우주에 존재하는 별자리의 총 수 n이 주어진다. (1 ≤ n ≤ 10⁶) 별의 수의 총합은 10⁶을 넘지 않는다.

두 번째 줄부터는 각 별자리의 정보가 주어진다.

각 별자리마다, 첫 번째 줄에는 별자리를 구성하는 별의 수 s가 주어진다. (1 ≤ s ≤ 30)

이후 s − 1개의 줄에 별들 사이의 연결 관계를 의미하는 두 정수 u, v가 주어진다. (0 ≤ u, v < s, u ≠ v)

편의를 위해 각 별자리 안에서 별들은 0, 1, 2, ⋯, s − 1번으로 번호가 붙어 있다고 생각하며, u v는 u번 별과 v번 별이 연결되어 있다는 의미이다. 별자리의 위상을 고려할 때는 별의 번호는 고려하지 않는다.

한나가 찍을 사진의 최대 장 수를 출력한다.