赤黒木というデータ構造をご存知でしょうか？この問題では赤または黒の頂点を持つ木を考えますが、心配は無用です。もし前述の構造について聞いたことがあっても、すぐに忘れてしまうのが一番です。

あなたは、各頂点が赤または黒のいずれか一方の色で塗られた木（閉路のない連結無向グラフ）を与えられます。実行できる操作は、辺で結ばれた2つの頂点 $v$ と $u$ を選び、$v$ を $u$ の色で塗り替えることです。

あなたのタスクは、初期状態からいくつかの（0回でもよい）操作を繰り返すことで、与えられた最終的な色の構成を得ることが可能かどうかを判定することです。

入力

入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 10^5$) が含まれます。

続いて各テストケースの説明が続きます。各テストケースの最初の行には、木の頂点数 $n$ ($1 \le n \le 10^5$) が含まれます。

次の行には、$n$ 文字からなる文字列が含まれます。各文字は 0 または 1 です。$i$ 番目の文字が 0 ならば $i$ 番目の頂点は初期状態で赤く塗られており、1 ならば黒く塗られています。

次の行には、$n$ 文字からなる文字列が含まれます。各文字は 0 または 1 であり、操作後に各頂点が赤（0）であるべきか黒（1）であるべきかを示します。

続く $n-1$ 行には、それぞれ2つの整数が含まれます。$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

注記

例の解説：最初のテストケースでは、まず3番目の頂点を2番目の頂点の色で塗り替え、次に4番目の頂点を2番目の頂点の色で塗り替えることができます。こうすることで、黒色の頂点は1番目だけになります。したがって、最後に2番目の頂点を1番目の頂点の色で塗り替えれば十分です。これら3回の操作の後、すべての頂点の色は与えられた最終構成と一致します。

2番目のテストケースでは、操作を行う必要はありません。両方の頂点は最初から正しい色になっています。

3番目のテストケースでは、頂点の色を入れ替えることは不可能です。