Czy znana Ci jest struktura danych zwana drzewem czerwono-czarnym? W tym zadaniu będziemy rozważali drzewa o czerwonych lub czarnych wierzchołkach, ale spokojnie, jeśli słyszałeś o wspomnianej strukturze, to najlepiej szybko o niej zapomnij.

Dane jest drzewo (czyli spójny graf nieskierowany bez cykli), w którym każdy wierzchołek jest pomalowany na jeden z dwóch kolorów – czerwony lub czarny. Operacją jaką możesz wykonać jest wybranie dwóch wierzchołków $v$ i $u$, połączonych krawędzią, i przemalowanie $v$ na kolor na który pomalowany jest $u$.

Twoim zadaniem jest stwierdzić, czy po pewnym (być może pustym) ciągu operacji z początkowego układu kolorów da się uzyskać zadany, końcowy układ.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $t$ ($1 \le t \le 10^5$), oznaczająca liczbę przypadków testowych.

Dalej następują opisy przypadków testowych. Opis przypadku testowego zaczyna się od wiersza z jedną liczbą całkowitą $n$ ($1 \le n \le 10^5$), oznaczającą liczbę wierzchołków w drzewie.

Kolejny wiersz zawiera słowo składające się z $n$ znaków, z których każdy to 0 lub 1. Jeśli $i$-ty znak to 0, to $i$-ty wierzchołek początkowo jest pomalowany na czerwono. Jeśli $i$-ty znak to 1, to $i$-ty wierzchołek początkowo jest pomalowany na czarno.

Następny wiersz zawiera słowo składające się z $n$ znaków, z których każdy to 0 lub 1, które w identyczny sposób opisuje czy każdy wierzchołek po zakończeniu wykonywania operacji powinien być czerwony czy czarny, gdzie również 0 oznacza kolor czerwony, a 1 oznacza kolor czarny.

W kolejnych $n-1$ liniach znajdują się po dwie liczby całkowite. $j$-ta z tych linii zawiera liczby całkowite $a_j$ oraz $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$) oznaczające, że wierzchołki $a_j$ oraz $b_j$ są połączone krawędzią. Możesz założyć, że dany ciąg krawędzi opisuje poprawne drzewo.

Suma wartości $n$ we wszystkich przypadkach testowych nie przekroczy $10^6$.

Wyjście

Na wyjściu powinno znaleźć się $t$ wierszy. Jeśli w $k$-tym przypadku testowym da się doprowadzić drzewo do żądanego stanu, to w $k$-tym wierszu powinno znaleźć się pojedyncze słowo TAK. W przeciwnym wypadku powinno znaleźć się w nim pojedyncze słowo NIE.

Przykład

Wejście 1

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

Wyjście 1

TAK
TAK
NIE

Uwagi

Wyjaśnienie przykładu: W pierwszym przypadku testowym możemy najpierw przemalować trzeci wierzchołek na kolor drugiego wierzchołka, po czym przemalować czwarty wierzchołek na kolor drugiego wierzchołka. W ten sposób ostatnim pozostałym wierzchołkiem koloru czarnego jest wierzchołek pierwszy. Wystarczy zatem teraz przemalować drugi wierzchołek na kolor pierwszego wierzchołka. Po tych trzech operacjach wszystkie kolory wierzchołków zgadzają się z zadanym, końcowym układem.

W drugim przypadku testowym nie musimy wykonywać żadnych operacji – oba wierzchołki już początkowo mają odpowiedni kolor.

W trzecim przypadku testowym nie da się zamienić kolorów wierzchołków miejscami.