대칭 트리

정점에 색이 지정된 N개 노드의 트리가 주어질 때, 이를 대칭축이 있도록 2D 평면에 그릴 수 있는가?

엄밀히 말해, 각 정점에 2D 평면상의 위치를 다음 조건을 만족하도록 지정할 수 있을 때 트리는 선대칭이다.

• 모든 위치는 서로 다르다.

• 정점 $v_{i}$의 색이 C이고 좌표가 ($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}$')도 반드시 존재해야 한다.

• 간선을 양 끝 정점 사이의 직선으로 나타냈을 때, 어떤 두 간선도 인접한 간선이 끝점에서 맞닿는 곳을 제외하고는 어떠한 점도 공유하지 않는다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 60초. 2 ≤ N ≤ 12.

큰 데이터 세트

시간 제한: 120초. 2 ≤ N ≤ 10000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 트리의 정점 수를 나타내는 정수 N 하나가 포함된 줄로 시작한다.

그다음 N개의 줄이 주어지며, 각 줄에는 대문자 하나가 주어진다. i번째 줄은 i번째 노드의 색을 나타낸다.

그다음 N-1개의 줄이 주어지며, 각 줄에는 두 정수 i와 j가 주어진다(1 ≤ i < j ≤ N). 이는 트리에 i번째 정점에서 j번째 정점으로 이어지는 간선이 있음을 나타낸다. 이 간선들은 연결된 트리를 이룬다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호(1부터 시작)이고, y는 위 정의에 따라 트리가 선대칭이면 "SYMMETRIC", 그렇지 않으면 "NOT SYMMETRIC"이다.

첫 번째 경우는 다음과 같이 그릴 수 있다.

두 번째 경우에는 어떤 배치도 대칭축을 갖지 않는다.

세 번째 경우를 대칭축이 있도록 그리는 한 가지 방법은 다음과 같다.