1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
char d1[100010];
char d2[100010];
int sasiedzi[100010][2];
int stopien[100010];
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n, i, a, b, c1=0, c2=0, k1=0, k2=0, k3=0, k4=0, c3=0, p;
		scanf("%d", &n);
		for(i=1;i<=n;i++)
		{
			stopien[i]=0;
			sasiedzi[i][0]=0;
			sasiedzi[i][1]=0;
		}
		scanf("%s", d1+1);
		scanf("%s", d2+1);
		
		for(i=0;i<n-1;i++)
		{
			scanf("%d%d", &a, &b);
			stopien[a]++;
			stopien[b]++;
			if(stopien[a]>=3 || stopien[b]>=3)
				c1=1;
			if(d2[a]==d2[b])
				c2=1;
			if(sasiedzi[a][0]!=0)
				sasiedzi[a][1]=b;
			else
				sasiedzi[a][0]=b;
			
			if(sasiedzi[b][0]!=0)
				sasiedzi[b][1]=a;
			else
				sasiedzi[b][0]=a;
			
		}
		for(i=1;i<=n;i++)
		{
			if(d1[i]=='0')
				k1=1;
			else
				k2=2;
			if(d2[i]=='0')
				k3=1;
			else
				k4=1;
			if(d1[i]!=d2[i])
				c3=1;
		}
		if(k1<k3 || k2<k4)
		{
			printf("NIE\n");
			continue;
		}
		if(n==1)
		{
			printf("TAK\n");
			continue;
		}
		if(c3==0)
		{
			printf("TAK\n");
			continue;
		}
		if(c1==1)
		{
			if(c2==1)
				printf("TAK\n");
			else
				printf("NIE\n");
			continue;
		}
		//sciezka
		for(i=1;i<=n;i++)
			if(stopien[i]==1)
			{
				p=i;
				break;
			}
		int zlicz1=0, zlicz2=0;
		int pop=p, s=p;
		p=sasiedzi[p][0];
		for(i=2;i<=n;i++)
		{
			if(d1[pop]!=d1[p])
				zlicz1++;
			if(d2[pop]!=d2[p])
				zlicz2++;
			if(sasiedzi[p][0]==pop)
			{
				pop=p;
				p=sasiedzi[p][1];
			}
			else
			{
				pop=p;
				p=sasiedzi[p][0];
			}
		}
		if(zlicz1>zlicz2 ||(zlicz1==zlicz2 && d1[s]==d2[s]))
		{
			printf("TAK\n");
		}
		else
		{
			printf("NIE\n");
		}
	}
	
}