28254번 - 트리와 깃발

문제

머슥은 $N$개의 정점이 있는 트리와 $M$종류의 깃발들을 가지고 있다. 깃발의 종류는 1ドル$부터 $M$까지의 정수로 표현된다. 각 정점은 0ドル$개 이상 $M$개 이하의 서로 다른 깃발을 가질 수 있다.

주어진 트리에서 두 개의 서로 다른 정점을 선택하고, 각 정점에서 깃발을 하나씩 선택할 때, 두 깃발이 같은 종류라면 두 정점을 잇는 간선을 추가할 수 있다.

주어진 트리에서 각 간선을 제거했을 때, 위 조건에 따라 깃발을 선택하여 간선을 추가하면 다시 하나의 트리가 되도록 깃발을 고르는 경우의 수를 구하여라.

입력

첫째 줄에 $N,\ M$이 공백을 사이에 두고 주어진다. $(2 \le N \le 500\ 000;$ 1ドル \le M \le 500\ 000)$

둘째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선들이 주어진다. $i$번째 줄에는 두 개의 정수 $A_i,ドル $B_i$가 공백을 사이에 두고 주어진다. 이는 $i$번 간선이 $A_i$번 정점과 $B_i$번 정점을 연결함을 의미한다. $(1 \le A_i,\ B_i \le N;$ 1ドル \le i \lt N;$ $A_i \ne B_i)$

이어서 $M$개의 줄에 걸쳐 $j$번째 줄에는 $C_j$ 와 종류가 $j$인 깃발을 가지고 있는 $C_j$개의 서로 다른 정점들이 공백을 사이에 두고 주어진다. $(0 \le C_j \le 500\ 000$; 1ドル \le j \le M;$ $\sum_{j=1}^{M}C_j \le 500\ 000)$

출력

$N-1$개의 줄에 걸처 $i$번째 줄에 트리의 $i$번 간선을 제거했을 때, 다시 하나의 트리가 되도록 깃발을 고르는 경우의 수를 구하여라.

제한

힌트