Bạn có quen thuộc với cấu trúc dữ liệu cây đỏ-đen không? Trong bài toán này, chúng ta sẽ xem xét các cây có các đỉnh được tô màu đỏ hoặc đen, nhưng đừng lo lắng—nếu bạn đã từng nghe về cấu trúc nêu trên, tốt nhất là hãy nhanh chóng quên nó đi.

Bạn được cho một cây (một đồ thị vô hướng liên thông không có chu trình) trong đó mỗi đỉnh được tô một trong hai màu: đỏ hoặc đen. Thao tác bạn có thể thực hiện là chọn hai đỉnh $v$ và $u$ được nối với nhau bằng một cạnh và tô lại màu cho $v$ bằng màu của $u$.

Nhiệm vụ của bạn là xác định xem liệu có thể đạt được cấu hình màu cuối cùng cho trước từ một cấu hình ban đầu sau một chuỗi các thao tác (có thể là rỗng) hay không.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^5$), đại diện cho số lượng bộ dữ liệu.

Các mô tả của các bộ dữ liệu sẽ theo sau. Mỗi mô tả bộ dữ liệu bắt đầu bằng một dòng chứa một số nguyên duy nhất $n$ ($1 \le n \le 10^5$), đại diện cho số lượng đỉnh trong cây.

Dòng tiếp theo chứa một chuỗi gồm $n$ ký tự, mỗi ký tự là 0 hoặc 1. Nếu ký tự thứ $i$ là 0, thì đỉnh thứ $i$ ban đầu được tô màu đỏ. Nếu ký tự thứ $i$ là 1, thì đỉnh thứ $i$ ban đầu được tô màu đen.

Dòng tiếp theo chứa một chuỗi gồm $n$ ký tự, mỗi ký tự là 0 hoặc 1, mô tả theo cách tương tự xem mỗi đỉnh nên là màu đỏ hay đen sau khi thực hiện các thao tác, trong đó 0 cũng biểu thị màu đỏ và 1 biểu thị màu đen.

$n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên. Dòng thứ $j$ trong số này chứa các số nguyên $a_j$ và $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$), chỉ ra rằng các đỉnh $a_j$ và $b_j$ được nối với nhau bằng một cạnh. Bạn có thể giả định rằng chuỗi các cạnh đã cho mô tả một cây hợp lệ.

Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Dữ liệu ra nên chứa $t$ dòng. Nếu trong bộ dữ liệu thứ $k$, có thể đưa cây về trạng thái mong muốn, dòng thứ $k$ nên chứa từ duy nhất TAK. Nếu không, nó nên chứa từ duy nhất NIE.

Ví dụ

Ví dụ 1

3
4
1011
1100
1 2
2 3
2 4
2
10
10
1 2
2
10
01
1 2

Kết quả 1

TAK
TAK
NIE

Ghi chú

Giải thích ví dụ: Trong bộ dữ liệu đầu tiên, trước tiên chúng ta có thể tô lại đỉnh thứ ba bằng màu của đỉnh thứ hai, và sau đó tô lại đỉnh thứ tư bằng màu của đỉnh thứ hai. Bằng cách này, đỉnh màu đen cuối cùng còn lại là đỉnh thứ nhất. Do đó, bây giờ chỉ cần tô lại đỉnh thứ hai bằng màu của đỉnh thứ nhất là đủ. Sau ba thao tác này, tất cả các màu của đỉnh đều khớp với cấu hình cuối cùng đã cho.

Trong bộ dữ liệu thứ hai, chúng ta không cần thực hiện bất kỳ thao tác nào – cả hai đỉnh đều đã có màu chính xác ngay từ đầu.

Trong bộ dữ liệu thứ ba, không thể hoán đổi màu của các đỉnh.