대칭 트리 (라지)

정점마다 색이 하나씩 칠해진 정점 $N$개짜리 트리가 있다. 이 트리를 평면에 대칭축이 있도록 그릴 수 있는지 판정하라.

정확히 말하면, 트리가 선대칭이라는 것은 각 정점에 평면 위의 위치를 하나씩 배정해서 다음 네 조건을 모두 만족시킬 수 있다는 뜻이다.

• 모든 위치는 서로 다르다.
• 색이 $C$인 정점 $v_i$의 좌표가 $(x_i, y_i)$이면, 색이 $C$이고 좌표가 $(-x_i, y_i)$인 정점 $v_i'$도 있어야 한다. $x_i$가 0이면 $v_i$와 $v_i'$는 같은 정점이다.
• 간선 $(v_i, v_j)$가 있으면 간선 $(v_i', v_j')$도 있어야 한다.
• 각 간선을 두 끝 정점을 잇는 선분으로 그렸을 때, 서로 다른 두 간선은 어떤 점도 공유하지 않는다. 단, 이웃한 두 간선이 공통 끝점에서 만나는 것은 허용한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 트리의 정점 수 $N$이 주어진다.

다음 $N$개의 줄에는 각각 대문자 하나가 주어진다. $i$번째 줄은 $i$번 정점의 색이다.

다음 $N-1$개의 줄에는 각각 정수 두 개 $i$와 $j$ ($1 \le i < j \le N$)가 주어진다. $i$번 정점과 $j$번 정점을 잇는 간선이 있다는 뜻이다. 주어지는 간선은 항상 연결된 트리를 이룬다.

제한:

• $1 \le T \le 100$
• $2 \le N \le 10000$

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 트리가 위 정의에 따라 선대칭이면 SYMMETRIC, 아니면 NOT SYMMETRIC이다.

예제 입력의 첫 번째 테스트 케이스는 다음과 같이 그릴 수 있다.

두 번째 테스트 케이스는 어떻게 배치해도 대칭축이 생기지 않는다.

세 번째 테스트 케이스를 대칭축이 있도록 그리는 방법 하나는 다음과 같다.