닮은 트리 세기

트리 $T = (V, E)$는 사이클이 없는 연결 그래프다. 여기서 $V = \{v_1, v_2, \ldots, v_n\}$은 정점 집합이고 $E = \{e_1, e_2, \ldots, e_{n-1}\}$은 간선 집합이다. 라벨이 붙은 트리는 정점마다 서로 다른 정수 하나가 붙어 있는 트리다. 즉 일대일 함수 $m_T : V \to \mathbb{Z}$가 하나 주어진다.

$u, v \in V$에 대해 $d_T(u, v) = m_T(u) - m_T(v)$로 정의한다. 라벨이 붙은 두 트리 $T_1 = (V_1, E_1)$과 $T_2 = (V_2, E_2)$가 다음 세 조건을 모두 만족하면 서로 닮았다고 한다.

1. $|V_1| = |V_2|$이다.
2. 전단사 함수 $f : V_1 \to V_2$가 있어서, $(u, v) \in E_1$인 것과 $(f(u), f(v)) \in E_2$인 것이 서로 동치다. 즉 두 트리는 동형이다.
3. 모든 $(u, v) \in E_1$에 대해 $d_{T_1}(u, v) = d_{T_2}(f(u), f(v))$이다.

그림 1: 서로 닮은 트리 $T_1$과 $T_2$.

그림 1의 두 트리는 이 정의에 따라 닮았고, $f$는 그림에 그려진 대응이다. 예를 들어 $d_{T_1}(v_1, v_2) = 1 - 9 = -8 = 9 - 17 = d_{T_2}(v_4, v_5)$이고, $d_{T_1}(v_2, v_4) = 9 - 6 = 3 = 17 - 14 = d_{T_2}(v_5, v_1)$이고, $d_{T_1}(v_2, v_3) = 9 - 7 = 2 = 17 - 15 = d_{T_2}(v_5, v_3)$이다.

라벨이 붙은 트리 $d$개가 주어진다. 닮음은 동치관계이므로 트리는 서로 닮은 것끼리 그룹으로 나뉜다. 각 그룹의 크기를 구하라.

첫 줄에 라벨이 붙은 트리의 개수 $d$가 주어진다 ($1 \le d \le 100$). 이어서 트리를 하나씩 두 줄로 나타낸다.

트리의 첫 줄에는 그 트리의 간선이 모두 놓인다. 간선 하나를 양 끝 정점의 번호 두 개로 나타내므로, 정점이 $n$개인 트리에서는 이 줄에 정수가 $2(n-1)$개 놓인다. 정점 번호는 $1$부터 $n$까지다. $n$을 따로 주지 않으므로 이 줄에 놓인 정수의 개수로 알아내야 한다. 트리의 두 번째 줄에는 정점 $v_1, v_2, \ldots, v_n$의 라벨 $m(v_1), m(v_2), \ldots, m(v_n)$이 이 순서로 주어진다.

$2 \le n \le 70000$이고 $-100000 < m(v_i) < 100000$이다. 한 트리 안의 라벨은 모두 다르다.

각 그룹의 크기를 작은 것부터 차례로 한 줄에 공백으로 구분해 출력한다. 같은 크기가 여러 번 나올 수 있다. 어떤 트리와도 닮지 않은 트리는 크기가 $1$인 그룹이 되고, 출력한 수의 합은 $d$다.