#include <cstdio> #include <vector> using namespace std; int main() { int q, n; char c; vector<char> B, E; scanf("%d", &q); for (int z=0;z<q;z++) { B.clear(); E.clear(); scanf("%d", &n); bool full0 = true, full1 = true, full0e = true, full1e = true; for (int i=0;i<n;i++) {scanf(" %c", &c); B.push_back(c); if (c=='1') full0 = false; else full1 = false;} for (int i=0;i<n;i++) {scanf(" %c", &c); E.push_back(c); if (c=='1') full0e = false; else full1e = false;} vector<int> C[n+1]; int t1, t2; bool pat = true; for (int i=1;i<n;i++) { scanf("%d %d", &t1, &t2); C[t1].push_back(t2); C[t2].push_back(t1); if (C[t1].size() > 2 || C[t2].size() > 2) pat = false; } bool fl = true; for (int i=0;i<n;i++) { if (B[i] != E[i]) {fl = false; break;} } if (fl) {printf("TAK\n"); continue;} if ((full0 && !full0e) || (full1 && !full1e)) {printf("NIE\n"); continue;} if (pat) { int rv1 = 0, rv2 = 0, beg1 = -1; for (int i=1;i<=n;i++) for (int j=0;j<C[i].size();j++) if (B[i-1] != B[C[i][j]-1]) rv1++; for (int i=1;i<=n;i++) { if (C[i].size() == 1) { beg1 = i; } for (int j=0;j<C[i].size();j++) if (E[i-1] != E[C[i][j]-1]) rv2++; } if (rv1 < rv2) printf("NIE\n"); else if (rv1 > rv2) printf("TAK\n"); else { if (B[beg1-1] == E[beg1-1]) printf("TAK\n"); else printf("NIE\n"); } } else { bool broken = false; for (int i=1;i<=n;i++) { if (broken) break; for (int j=0;j<C[i].size();j++) { if (E[i-1] == E[C[i][j]-1]) {broken = true; break;} } } printf(broken ? "TAK\n" : "NIE\n"); } } }
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 | #include <cstdio> #include <vector> using namespace std; int main() { int q, n; char c; vector<char> B, E; scanf("%d", &q); for (int z=0;z<q;z++) { B.clear(); E.clear(); scanf("%d", &n); bool full0 = true, full1 = true, full0e = true, full1e = true; for (int i=0;i<n;i++) {scanf(" %c", &c); B.push_back(c); if (c=='1') full0 = false; else full1 = false;} for (int i=0;i<n;i++) {scanf(" %c", &c); E.push_back(c); if (c=='1') full0e = false; else full1e = false;} vector<int> C[n+1]; int t1, t2; bool pat = true; for (int i=1;i<n;i++) { scanf("%d %d", &t1, &t2); C[t1].push_back(t2); C[t2].push_back(t1); if (C[t1].size() > 2 || C[t2].size() > 2) pat = false; } bool fl = true; for (int i=0;i<n;i++) { if (B[i] != E[i]) {fl = false; break;} } if (fl) {printf("TAK\n"); continue;} if ((full0 && !full0e) || (full1 && !full1e)) {printf("NIE\n"); continue;} if (pat) { int rv1 = 0, rv2 = 0, beg1 = -1; for (int i=1;i<=n;i++) for (int j=0;j<C[i].size();j++) if (B[i-1] != B[C[i][j]-1]) rv1++; for (int i=1;i<=n;i++) { if (C[i].size() == 1) { beg1 = i; } for (int j=0;j<C[i].size();j++) if (E[i-1] != E[C[i][j]-1]) rv2++; } if (rv1 < rv2) printf("NIE\n"); else if (rv1 > rv2) printf("TAK\n"); else { if (B[beg1-1] == E[beg1-1]) printf("TAK\n"); else printf("NIE\n"); } } else { bool broken = false; for (int i=1;i<=n;i++) { if (broken) break; for (int j=0;j<C[i].size();j++) { if (E[i-1] == E[C[i][j]-1]) {broken = true; break;} } } printf(broken ? "TAK\n" : "NIE\n"); } } } |