¿Estás familiarizado con la estructura de datos conocida como árbol rojo-negro? En este problema, consideraremos árboles con vértices rojos o negros, pero no te preocupes: si has oído hablar de la estructura mencionada, es mejor que te olvides rápidamente de ella.

Se te da un árbol (un grafo conexo no dirigido sin ciclos) en el que cada vértice está pintado de uno de dos colores: rojo o negro. La operación que puedes realizar consiste en elegir dos vértices $v$ y $u$ conectados por una arista y volver a pintar $v$ con el color con el que está pintado $u$.

Tu tarea es determinar si es posible obtener una configuración final de colores dada a partir de una configuración inicial después de alguna secuencia (posiblemente vacía) de operaciones.

Entrada

La primera línea de la entrada contiene un único entero $t$ ($1 \le t \le 10^5$), que representa el número de casos de prueba.

A continuación siguen las descripciones de los casos de prueba. Cada descripción de caso de prueba comienza con una línea que contiene un único entero $n$ ($1 \le n \le 10^5$), que representa el número de vértices en el árbol.

La siguiente línea contiene una cadena que consta de $n$ caracteres, cada uno de los cuales es 0 o 1. Si el $i$-ésimo carácter es 0, entonces el $i$-ésimo vértice está pintado inicialmente de rojo. Si el $i$-ésimo carácter es 1, entonces el $i$-ésimo vértice está pintado inicialmente de negro.

La siguiente línea contiene una cadena que consta de $n$ caracteres, cada uno de los cuales es 0 o 1, que describe de la misma manera si cada vértice debe ser rojo o negro después de realizar las operaciones, donde 0 también denota rojo y 1 denota negro.

Las siguientes $n-1$ líneas contienen cada una dos enteros. La $j$-ésima de estas líneas contiene los enteros $a_j$ y $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$), indicando que los vértices $a_j$ y $b_j$ están conectados por una arista. Puedes asumir que la secuencia de aristas dada describe un árbol válido.

La suma de $n$ sobre todos los casos de prueba no supera $10^6$.

Salida

La salida debe contener $t$ líneas. Si en el $k$-ésimo caso de prueba es posible llevar el árbol al estado deseado, la $k$-ésima línea debe contener la palabra TAK. De lo contrario, debe contener la palabra NIE.

Ejemplos

Ejemplos 1

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

Salida 1

TAK
TAK
NIE

Nota

Explicación del ejemplo: En el primer caso de prueba, podemos primero volver a pintar el tercer vértice con el color del segundo vértice, y luego volver a pintar el cuarto vértice con el color del segundo vértice. De esta manera, el último vértice restante de color negro es el primer vértice. Por lo tanto, es suficiente volver a pintar el segundo vértice con el color del primer vértice. Después de estas tres operaciones, todos los colores de los vértices coinciden con la configuración final dada.

En el segundo caso de prueba, no necesitamos realizar ninguna operación: ambos vértices ya tienen el color correcto inicialmente.

En el tercer caso de prueba, no es posible intercambiar los colores de los vértices.