대칭 트리 (Small)

정점마다 색이 칠해진 정점 $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$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

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

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

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

제한

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$ 는 $1$ 부터 시작하는 테스트 케이스 번호이고, $y$ 는 트리가 위 정의대로 축 대칭이면 SYMMETRIC, 아니면 NOT SYMMETRIC이다.

첫 번째 테스트 케이스는 다음과 같이 그릴 수 있다.

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

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