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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

// #define int long long

// const int P = 1e9+7;


vector<int> generate_order(const vector<vector<int>>& tree)
{
    int begin = 0;
    for(int i=1; i<tree.size(); i++)
    {
        if(tree[i].size() == 1) { begin = i; break; }
    }

    int current = begin;
    vector<int> result = {current};
    int prev = -1;
    while(true)
    {
        int x = tree[current][0];
        if(x == prev)
        {
            if(tree[current].size() == 1) return result;
            x = tree[current][1];
        }
        result.push_back(x);
        prev = current;
        current = x;
    }
    assert(false);
}

vector<vector<int>> readTree(int n)
{
    vector<vector<int>> tree;
    tree.resize(n+1);

    for(int i=1; i<n; i++)
    {
        int a,b; cin >> a >> b;
        tree[a].push_back(b); tree[b].push_back(a);
    }
    return tree;
}

bool isAlternate(const vector<vector<int>>& tree, const string& target)
{
    // cerr << "isAlternate " << endl;
    for(int i=1; i<tree.size(); i++)
        for(int x : tree[i])
            if(target[i-1] == target[x-1])
                return false;
    // cerr << "true" << endl;
    return true;
}

bool solve()
{
    int n; cin >> n;
    string input, target;
    cin >> input >> target;
    // cerr << "solving: " << n << " " << input << " " << target << endl;
    bool input_has_both = false;
    bool target_has_both = false;
    for(int i=1; i<input.size(); i++)
    {
        if (input[i] != input[i-1]) input_has_both = true;
        if (target[i] != target[i-1]) target_has_both = true;
    }

    vector<vector<int>> tree = readTree(n);
    if(input == target) return true;
    // we can easily color all in single color
    if(input_has_both && !target_has_both) return true;
    // not equal and input has a single color
    if(!input_has_both) return false;

    // cerr << n << endl;

    // if not a line we can return true assuming target has any two consecutive
    bool not_a_line = false;
    for(int i=1; i<=n; i++)
        if(tree[i].size() > 2) not_a_line = true;

    if(not_a_line)
    {
        if(isAlternate(tree, target))
            return false;
        // cerr << "waht " << endl;
        return true;
    }

    // check the ordering
    vector<int> order = generate_order(tree);
    assert(order.size() == n);

    string reordered1, reordered2;
    for(int x : order)
    {
        reordered1.push_back(input[x-1]);
        reordered2.push_back(target[x-1]);
    }
    // cerr << reordered1 << " " << reordered2 << endl;
    auto ct_changes = [](const string& s) -> int {
        int result = 0;
        for(int i=1; i<s.size(); i++)
            if(s[i] != s[i-1])
                ++result;
        return result;
    };

    int ch1 = ct_changes(reordered1);
    int ch2 = ct_changes(reordered2);

    if(reordered1[0] != reordered2[0])
        ch1--;
    if(reordered1.size() > 1 && reordered1.back() != reordered2.back())
    {
        ch1--;
    }
    return ch1 >= ch2;
}

int main()
{
ios_base::sync_with_stdio(false);

int t; cin >> t; while(t--)
{
    if(solve())
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;
}

return 0;
}