#include<bits/stdc++.h> using namespace std; bool P[(int)1e5+5],K[(int)1e5+5]; int DEG[(int)1e5+5]; int main(){ ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); int t;cin>>t; while(t--){ int n;cin>>n; bool roz=0; bool trioi=0; bool homo=0; bool poli=0; int khetero=0,phetero=0; string p,k;cin>>p>>k; //cout<<p<<" "<<k<<"\n"; for(int i=0;i<n;i++){ if(p[i]=='1')P[i+1]=1; else P[i+1]=0; if(k[i]=='1')K[i+1]=1; else K[i+1]=0; if(P[i+1]!=K[i+1])roz=1; DEG[i+1]=0; if(i!=0 and P[i]!=P[i+1])poli=1; } //cout<<k[0]<<" "<<k[1]<<"\n"; for(int i=1;i<n;i++){ int a,b;cin>>a>>b; DEG[a]++;DEG[b]++; if(DEG[a]==3 or DEG[b]==3)trioi=1; if(K[a]==K[b])homo=1; else khetero++; if(P[a]!=P[b])phetero++; } //cout<<K[1]<<" "<<K[2]<<"\n"; //cout<<homo<<"\n"; bool odp=0; if(!roz)odp=1; else if(!poli)odp=0; else if(!homo)odp=0; else if(trioi)odp=1; else if(phetero>khetero)odp=1; else if(phetero<khetero)odp=0; else{ for(int i=1;i<=n;i++){ if(DEG[i]==1){ if(P[i]==K[i])odp=1; break; } if(i==n)odp=1; } } if(odp)cout<<"TAK\n"; else cout<<"NIE\n"; } return 0; }
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 | #include<bits/stdc++.h> using namespace std; bool P[(int)1e5+5],K[(int)1e5+5]; int DEG[(int)1e5+5]; int main(){ ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); int t;cin>>t; while(t--){ int n;cin>>n; bool roz=0; bool trioi=0; bool homo=0; bool poli=0; int khetero=0,phetero=0; string p,k;cin>>p>>k; //cout<<p<<" "<<k<<"\n"; for(int i=0;i<n;i++){ if(p[i]=='1')P[i+1]=1; else P[i+1]=0; if(k[i]=='1')K[i+1]=1; else K[i+1]=0; if(P[i+1]!=K[i+1])roz=1; DEG[i+1]=0; if(i!=0 and P[i]!=P[i+1])poli=1; } //cout<<k[0]<<" "<<k[1]<<"\n"; for(int i=1;i<n;i++){ int a,b;cin>>a>>b; DEG[a]++;DEG[b]++; if(DEG[a]==3 or DEG[b]==3)trioi=1; if(K[a]==K[b])homo=1; else khetero++; if(P[a]!=P[b])phetero++; } //cout<<K[1]<<" "<<K[2]<<"\n"; //cout<<homo<<"\n"; bool odp=0; if(!roz)odp=1; else if(!poli)odp=0; else if(!homo)odp=0; else if(trioi)odp=1; else if(phetero>khetero)odp=1; else if(phetero<khetero)odp=0; else{ for(int i=1;i<=n;i++){ if(DEG[i]==1){ if(P[i]==K[i])odp=1; break; } if(i==n)odp=1; } } if(odp)cout<<"TAK\n"; else cout<<"NIE\n"; } return 0; } |