트리 라벨링

트리 $T = (V, E)$가 있다. $V$는 정점의 집합이고 $E$는 간선의 집합이다. 간선으로 $v$와 이어진 정점을 $T$에서 $v$의 이웃이라 하고, $v$의 이웃을 모두 모은 집합을 $N(v)$로 쓴다.

$T$의 라벨링은 일대일 대응 함수 $f : V \to \{1, 2, \dots, |V|\}$이다.

두 라벨링 $f$와 $g$가 다음 조건을 만족하면 서로 동치라고 한다. 모든 정점 $u \in V$에 대해, $f(u) = g(v)$이고 $\{f(u') \mid u' \in N(u)\} = \{g(v') \mid v' \in N(v)\}$인 정점 $v \in V$가 존재한다. 이 정의에 따라 라벨링 $f$는 자기 자신과 동치이다.

아래 그림은 서로 동치인 두 라벨링이다.

트리 $T$와 $T$의 라벨링 $f$가 주어질 때, $f$와 동치인 라벨링의 개수를 세는 프로그램을 작성하라. $f$ 자신도 $f$와 동치이므로 개수에 포함한다.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 트리의 정점 개수 $N$ ($1 \le N \le 1000$)이 주어진다. 이어지는 $N-1$개의 줄에는 각각 두 정수 $i$와 $j$ ($1 \le i, j \le N$)가 주어지며, 정점 $i$와 정점 $j$를 잇는 간선을 뜻한다. 그다음 줄에는 라벨링을 나타내는 정수 $N$개가 주어지고, 그중 $i$번째 수는 정점 $i$의 라벨이다. 모든 정수는 공백 하나로 구분된다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 $f$와 동치인 라벨링의 개수를 한 줄에 출력한다. 이 개수는 매우 커질 수 있으므로 나머지 연산 없이 정확한 값을 출력한다.