생성 트리

텍사스주 메드퍼드의 크리스마스에 Meemaw Cooper는 아주 특별한 배선으로 크리스마스 전구를 단 아름다운 나무를 오랜 시간 준비했다. Meemaw가 집 밖에 있는 사이 손녀 Missy가 실수로 나무를 건드려 전구가 망가졌다. Missy는 Meemaw가 돌아오기 전에 원래 배선을 되살리고 싶어 했고, 배선이 어떻게 만들어졌는지 아는 오빠 Sheldon에게 도움을 청했다.

Meemaw는 같은 배선의 전구 세트를 여러 개 사서 한데 이어 붙였다. 전구 배선은 트리(무방향 비순환 연결 그래프)로 볼 수 있다. 정점은 전구이고 간선은 전구를 잇는 전선이다. 각 간선은 서로 다른 두 전구를 잇고, 간선들의 집합은 트리를 이룬다. Meemaw는 서로 다른 복사본 사이에 전선을 추가해서, 전체 배선이 다시 트리가 되도록 만들었다.

Sheldon은 Missy에게 복구 방법을 설명한 뒤, 오후 내내 이 문제를 일반화한 버전을 생각했다. 트리 N개로 이루어진 모음이 주어졌을 때, 각 트리에 대해 모음 속 다른 트리 중 그 트리를 만들어 낼 수 있는 트리가 몇 개인지 구하라. 트리 T1이 트리 T2를 만들어 낼 수 있다는 것은, T1의 복사본 하나 이상을 간선으로 연결해 T2와 동형인 트리를 얻을 수 있다는 뜻이다. 간선은 제거할 수 없고 추가만 할 수 있다. 두 트리가 동형이라는 것은 정점에 번호를 다시 붙여 두 트리가 완전히 같아질 수 있다는 뜻이다. 예를 들어 간선 {(1, 2), (2, 3)}을 가진 트리는 간선 {(1, 3), (3, 2)}를 가진 트리와 동형이다.

아래 그림은 트리 4개(N = 4)로 이루어진 모음을 보여준다. 트리 1은 모음의 다른 어떤 트리로도 만들어 낼 수 없다. 트리 2는 트리 1로 만들 수 있다. 트리 3은 트리 4로, 트리 4는 트리 3으로 만들 수 있다.

첫 줄에 정수 $N$ ($2 \le N \le 2 \times 10^5$)이 주어진다. 이어서 $N$개의 묶음이 주어지며, 각 묶음은 트리 하나를 나타낸다. 각 묶음의 첫 줄에는 정점 개수 $K$ ($2 \le K \le 2 \times 10^5$)가 주어진다. 정점은 1부터 $K$까지의 서로 다른 정수로 표현된다. 다음 $K - 1$개의 줄에는 간선 $(U, V)$를 나타내는 정수 $U$, $V$ ($1 \le U, V \le K$, $U \ne V$)가 주어진다. 모든 트리의 정점 개수 합은 $4 \times 10^5$을 넘지 않는다.

한 줄에 정수 $N$개를 공백으로 구분해 출력한다. $i$번째 정수는 입력의 $i$번째 트리를 만들어 낼 수 있는 다른 트리의 개수이다.