만드는 중입니다

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

대칭 트리 (라지)

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

요약
색이 칠해진 트리를 평면에 연직 대칭선이 생기도록 그릴 수 있는지 판정합니다.
난이도

보통10점 중 7점

유형
트리, 재귀, 해시맵, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 수 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≤100002 \le N \le 10000

출력

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 트리가 위 정의에 따라 선대칭이면 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

    입력
    3
2
A
A
1 2
2
A
B
1 2
2
Q
Z
1 2
    예상 출력
    Case #1: SYMMETRIC
Case #2: SYMMETRIC
Case #3: SYMMETRIC