The Cave

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
const int LOG = 30;
vector<vector<int>> grafo;
array<array<int, LOG>, MAXN> dp;
array<int, MAXN> Prof;

void dfs(int v, int p)
{
    Prof[v] = Prof[p] + 1;
    dp[v][0] = p;
    for (int k = 1; k < LOG; k++) dp[v][k] = dp[dp[v][k-1]][k-1];

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v);
    }
}

int lca(int a, int b)
{
    if (Prof[a] < Prof[b]) swap(a, b);
    int jump = Prof[a] - Prof[b];
    for (int k = 0; k < LOG; k++)
        if (jump & (1 << k)) a = dp[a][k];
    if (a == b) return a;
    for (int k = LOG-1; k >= 0; k--)
        if (dp[a][k] != dp[b][k])
            a = dp[a][k], b = dp[b][k];
    return dp[a][0];
}

void solve()
{
    grafo.clear();
    int N, M;
    cin >> N >> M;
    grafo.resize(N+1);
    for (int i = 1; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[X].push_back(Y);
        grafo[Y].push_back(X);
    }
    Prof[1] = -1;
    dfs(1, 1);
    int atual = 1;
    vector<tuple<int, int, int> > sites(M+1);
    for (int i = 1; i <= M; i++)
    {
        int X, Y, D;
        cin >> X >> Y >> D;
        sites[i] = {X, Y, D};
        int L = lca(X, Y);
        D -= Prof[X] + Prof[Y] - 2*Prof[L];
        if (D < 0) {atual = -1; break;}
        D /= 2;
        for (int k = 0; k < LOG; k++)
            if (D & (1 << k)) L = dp[L][k];
        if (Prof[L] > Prof[atual]) atual = L;
    }
    if (atual == -1) {cout << "NIE" << '\n'; return;}
    Prof[atual] = -1;
    dfs(atual, atual);
    for (int i = 1; i <= M; i++)
    {
        auto [X, Y, D] = sites[i];
        if (Prof[X] + Prof[Y] > D) {cout << "NIE" << '\n'; return;}
    }
    cout << "TAK " << atual << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) solve();
}