Connaissez-vous la structure de données appelée arbre rouge-noir ? Dans ce problème, nous considérerons des arbres dont les sommets sont rouges ou noirs, mais ne vous inquiétez pas : si vous avez déjà entendu parler de la structure susmentionnée, il vaut mieux l'oublier rapidement.

On vous donne un arbre (un graphe connexe non orienté sans cycle) dans lequel chaque sommet est peint d'une de deux couleurs : rouge ou noir. L'opération que vous pouvez effectuer consiste à choisir deux sommets $v$ et $u$ reliés par une arête et à repeindre $v$ avec la couleur dont $u$ est peint.

Votre tâche est de déterminer s'il est possible d'obtenir une configuration finale de couleurs donnée à partir d'une configuration initiale après une séquence (éventuellement vide) d'opérations.

Entrée

La première ligne de l'entrée contient un entier unique $t$ ($1 \le t \le 10^5$), représentant le nombre de cas de test.

Les descriptions des cas de test suivent. Chaque description de cas de test commence par une ligne contenant un entier unique $n$ ($1 \le n \le 10^5$), représentant le nombre de sommets dans l'arbre.

La ligne suivante contient une chaîne composée de $n$ caractères, chacun étant 0 ou 1. Si le $i$-ième caractère est 0, alors le $i$-ième sommet est initialement peint en rouge. Si le $i$-ième caractère est 1, alors le $i$-ième sommet est initialement peint en noir.

La ligne suivante contient une chaîne composée de $n$ caractères, chacun étant 0 ou 1, qui décrit de la même manière si chaque sommet doit être rouge ou noir après avoir effectué les opérations, où 0 désigne également le rouge et 1 désigne le noir.

Les $n-1$ lignes suivantes contiennent chacune deux entiers. La $j$-ième de ces lignes contient les entiers $a_j$ et $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$), indiquant que les sommets $a_j$ et $b_j$ sont reliés par une arête. Vous pouvez supposer que la séquence d'arêtes donnée décrit un arbre valide.

La somme des $n$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

La sortie doit contenir $t$ lignes. Si, dans le $k$-ième cas de test, il est possible d'amener l'arbre à l'état souhaité, la $k$-ième ligne doit contenir le mot unique TAK. Sinon, elle doit contenir le mot unique NIE.

Exemples

Entrée 1

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

Sortie 1

TAK
TAK
NIE

Remarque

Explication de l'exemple : Dans le premier cas de test, nous pouvons d'abord repeindre le troisième sommet avec la couleur du deuxième sommet, puis repeindre le quatrième sommet avec la couleur du deuxième sommet. De cette façon, le dernier sommet restant de couleur noire est le premier sommet. Il suffit donc maintenant de repeindre le deuxième sommet avec la couleur du premier sommet. Après ces trois opérations, toutes les couleurs des sommets correspondent à la configuration finale donnée.

Dans le deuxième cas de test, nous n'avons besoin d'effectuer aucune opération – les deux sommets ont déjà la bonne couleur initialement.

Dans le troisième cas de test, il n'est pas possible d'échanger les couleurs des sommets.