你熟悉紅黑樹這種資料結構嗎？在本題中，我們將考慮頂點為紅色或黑色的樹，但別擔心——如果你聽過上述結構，最好趕快把它忘掉。

給你一棵樹（一個沒有環的連通無向圖），其中每個頂點都被塗成紅色或黑色兩種顏色之一。你可以執行的操作是選擇兩個由邊相連的頂點 $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 代表黑色，描述了執行操作後每個頂點應有的顏色。

接下來的 $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

說明

範例說明：在第一個測試案例中，我們可以先將第三個頂點重新塗上第二個頂點的顏色，然後將第四個頂點重新塗上第二個頂點的顏色。這樣一來，最後剩下的黑色頂點就是第一個頂點。因此，現在只需將第二個頂點重新塗上第一個頂點的顏色即可。經過這三次操作後，所有頂點的顏色都與給定的最終配置相符。

在第二個測試案例中，我們不需要執行任何操作——兩個頂點初始時就已經是正確的顏色了。

在第三個測試案例中，無法交換頂點的顏色。