Cho một cây gồm \(N\) nút có màu, liệu có thể vẽ cây này trên mặt phẳng 2D sao cho nó có một trục đối xứng hay không?

Một cách hình thức, một cây được gọi là đối xứng trục nếu mỗi đỉnh có thể được gán một vị trí trên mặt phẳng 2D sao cho:

• Tất cả các vị trí là phân biệt.
• Nếu đỉnh \(v_i\) có màu \(C\) và tọa độ \((x_i, y_i)\), thì phải tồn tại một đỉnh \(v_i'\) có màu \(C\) tại tọa độ \((-x_i, y_i)\) -- Lưu ý nếu \(x_i = 0\), \(v_i\) và \(v_i'\) là cùng một đỉnh.
• Với mỗi cạnh \((v_i, v_j)\), phải tồn tại một cạnh \((v_i', v_j')\).
• Nếu các cạnh được biểu diễn bằng các đoạn thẳng nối các đỉnh đầu mút, không có hai cạnh nào có điểm chung ngoại trừ tại các đầu mút của các cạnh kề nhau.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo.
Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\), số lượng đỉnh trong cây.
\(N\) dòng tiếp theo, mỗi dòng chứa một chữ cái in hoa duy nhất. Dòng thứ \(i\) đại diện cho màu của nút thứ \(i\).
\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1 \le i < j \le N\)). Điều này biểu thị rằng cây có một cạnh nối đỉnh thứ \(i\) và đỉnh thứ \(j\). Các cạnh sẽ tạo thành một cây liên thông.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là "SYMMETRIC" nếu cây đối xứng trục theo định nghĩa trên hoặc "NOT SYMMETRIC" nếu ngược lại.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset: \(2 \le N \le 12\).
• Large dataset: \(2 \le N \le 10000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Symmetric Trees.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.