레드-블랙 트리라는 자료구조에 대해 들어본 적이 있나요? 이 문제에서는 빨간색 또는 검은색 정점을 가진 트리를 다룰 것이지만, 걱정하지 마세요. 만약 앞서 언급한 자료구조에 대해 들어본 적이 있다면, 그것은 빨리 잊어버리는 것이 좋습니다.

트리(사이클이 없는 연결된 무방향 그래프)가 주어지며, 각 정점은 빨간색 또는 검은색 중 하나의 색으로 칠해져 있습니다. 수행할 수 있는 연산은 간선으로 연결된 두 정점 $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)이어야 하는 최종 상태를 동일한 방식으로 나타냅니다.

다음 $n-1$개의 줄에는 각각 두 개의 정수가 주어집니다. 이 중 $j$번째 줄은 정점 $a_j$와 $b_j$ ($1 \le a_j, b_j \le n; a_j \neq 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

참고

예제 설명: 첫 번째 테스트 케이스에서, 먼저 세 번째 정점을 두 번째 정점의 색으로 다시 칠하고, 그 다음 네 번째 정점을 두 번째 정점의 색으로 다시 칠할 수 있습니다. 이렇게 하면 검은색인 마지막 정점은 첫 번째 정점이 됩니다. 따라서 이제 두 번째 정점을 첫 번째 정점의 색으로 다시 칠하면 충분합니다. 이 세 번의 연산 후, 모든 정점의 색은 주어진 최종 구성과 일치하게 됩니다.

두 번째 테스트 케이스에서는 연산을 수행할 필요가 없습니다. 두 정점 모두 처음에 이미 올바른 색을 가지고 있기 때문입니다.

세 번째 테스트 케이스에서는 정점의 색을 서로 바꿀 수 없습니다.