트리와 깃발

머슥은 $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$번 간선을 제거했을 때, 다시 하나의 트리가 되도록 깃발을 고르는 경우의 수를 구하여라.