만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

대칭 트리 (Small)

시간 제한5초메모리 제한512 MB

요약
색이 칠해진 정점 12개 이하의 트리가 직선 간선으로 좌우 대칭되게 그려지는지 판정합니다.
난이도

보통10점 중 6점

유형
완전 탐색, 트리, 백트래킹
정답자
아직 제출이 없습니다

문제

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

정확히 말하면, 트리가 축 대칭이라는 것은 모든 정점에 평면 좌표를 하나씩 배정해서 다음 네 조건을 동시에 만족시킬 수 있다는 뜻이다.

  • 서로 다른 두 정점의 좌표는 항상 다르다.
  • 색이 CC인 정점 viv_i의 좌표가 (xi,yi)(x_i, y_i)이면, 색이 CC이면서 좌표가 (−xi,yi)(-x_i, y_i)인 정점 vi′v_i'도 존재한다. xix_i가 00이면 viv_i와 vi′v_i'은 같은 정점이다.
  • 간선 (vi,vj)(v_i, v_j)가 있으면 간선 (vi′,vj′)(v_i', v_j')도 있다.
  • 각 간선을 두 끝점을 잇는 선분으로 그렸을 때, 서로 다른 두 선분은 인접한 간선이 공유하는 끝점 말고는 어떤 점도 공유하지 않는다.

입력

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

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

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

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

제한

  • 1≤T≤1001 \le T \le 100
  • 2≤N≤122 \le N \le 12

출력

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

힌트

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

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

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

예제2

  1. 예제 1

    입력
    3
4
R
G
B
B
1 2
2 3
2 4
4
R
G
B
Y
1 2
2 3
2 4
12
Y
B
Y
G
R
G
Y
Y
B
B
B
R
1 3
1 9
1 10
2 3
3 7
3 8
3 11
4 8
5 7
6 7
8 12
    예상 출력
    Case #1: SYMMETRIC
Case #2: NOT SYMMETRIC
Case #3: SYMMETRIC

  2. 예제 2

    입력
    4
2
A
A
1 2
2
A
B
1 2
3
A
B
A
1 2
2 3
4
A
B
C
D
1 2
1 3
1 4
    예상 출력
    Case #1: SYMMETRIC
Case #2: SYMMETRIC
Case #3: SYMMETRIC
Case #4: NOT SYMMETRIC