Знакомы ли вы со структурой данных, известной как красно-черное дерево? В этой задаче мы будем рассматривать деревья с красными или черными вершинами, но не волнуйтесь — если вы слышали о вышеупомянутой структуре, лучше поскорее о ней забыть.

Вам дано дерево (связный неориентированный граф без циклов), в котором каждая вершина окрашена в один из двух цветов: красный или черный. Операция, которую вы можете выполнять, заключается в выборе двух вершин $v$ и $u$, соединенных ребром, и перекрашивании вершины $v$ в цвет, в который окрашена вершина $u$.

Ваша задача — определить, возможно ли получить заданную конечную конфигурацию цветов из начальной конфигурации после некоторой (возможно, пустой) последовательности операций.

Входные данные

Первая строка входных данных содержит единственное целое число $t$ ($1 \le t \le 10^5$), количество тестовых случаев.

Далее следуют описания тестовых случаев. Описание каждого тестового случая начинается со строки, содержащей единственное целое число $n$ ($1 \le n \le 10^5$), количество вершин в дереве.

Следующая строка содержит строку из $n$ символов, каждый из которых равен 0 или 1. Если $i$-й символ равен 0, то $i$-я вершина изначально окрашена в красный цвет. Если $i$-й символ равен 1, то $i$-я вершина изначально окрашена в черный цвет.

Следующая строка содержит строку из $n$ символов, каждый из которых равен 0 или 1, которая аналогичным образом описывает, в какой цвет (0 — красный, 1 — черный) должна быть окрашена каждая вершина после выполнения операций.

Следующие $n-1$ строк содержат по два целых числа. $j$-я из этих строк содержит целые числа $a_j$ и $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$), указывающие на то, что вершины $a_j$ и $b_j$ соединены ребром. Можно считать, что заданная последовательность ребер описывает корректное дерево.

Сумма $n$ по всем тестовым случаям не превышает $10^6$.

Выходные данные

Выходные данные должны содержать $t$ строк. Если в $k$-м тестовом случае возможно привести дерево к желаемому состоянию, $k$-я строка должна содержать единственное слово TAK. В противном случае она должна содержать единственное слово NIE.

Примеры

Входные данные 1

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

Выходные данные 1

TAK
TAK
NIE

Примечание

Пояснение к примеру: В первом тестовом случае мы можем сначала перекрасить третью вершину в цвет второй вершины, а затем перекрасить четвертую вершину в цвет второй вершины. Таким образом, единственной оставшейся вершиной черного цвета станет первая вершина. Поэтому теперь достаточно перекрасить вторую вершину в цвет первой вершины. После этих трех операций цвета всех вершин будут соответствовать заданной конечной конфигурации.

Во втором тестовом случае нам не нужно выполнять никаких операций — обе вершины изначально имеют правильный цвет.

В третьем тестовом случае поменять цвета вершин местами невозможно.