#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int128 __int128
const int N=1e5+5;
ll n,supd[N],m,fa[N],dep[N ],vis[N ],id[N],deg[N],rk[N],rem[N];
vector<int> g[N];
void dfs0(int u){
    for(auto v:g[u]){
        if(v == fa[u])continue;
        //if(id[v]==-1)continue;
        fa[v]=u;
        dfs0(v);
    }
}
void dfs(int u){
    rem[u]=1;
    if(id[u])return;
    for(auto v:g[u]){
        if(v == fa[u])continue;
        //if(id[v]==-1)continue;
        fa[v]=u;
        dep[v]=dep[u]+1;
        //printf("v=%d,dep[%d]=%lld\n",v,v,dep[v]);
        dfs(v);
    }
}

vector<ll> d[N ];
/*void dfs2(int u){
    for(auto v:g[u]){
        if(v == fa[u])continue;
        dfs2(v);
        
    }
}*/

void solve(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        g[i].clear();
        d[i].clear();
        vis[i]=0;
        id[i]=0;
        rem[i]=0;
        supd[i]=0;
        dep[i]=0;
        rk[i]=0;
    }
    for(int i=1;i<=m;i++){
        supd[i]=i+1;
        id[i]=i;
        rk[i]=i;
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v );
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs0(n);
    vector<int> d1;
    for(int i=1;i<=n;i++){
        deg[i]=g[i].size();
        if(g[i].size()==1)d1.push_back(i);
    }
    while(!d1.empty()){
        int u = d1.back();
        d1.pop_back();
        if(g[fa[u ]].size() != 2 || fa[u]==n)continue;
        id[fa[u]]=id[u];
        rk[id[u]]=fa[u];
        //id[u]=-1;
        deg[fa[u]]--;
        if(deg[fa[u ]]==1){
            d1.push_back(fa[u]);
        }
    }
    /*for(int i=1;i<=n;i++){
        printf("id[%d]=%lld\n",i,id[i]);
    }
    for(int i=1;i<=m;i++){
        printf("rk[%d]=%lld\n",i,rk[i]);
    }*/
    dep[n ]=0;
    dfs(n );
    vector<int> to_op;
    ll mxdep=0;
    for(int i=1;i<=n;i++){
        //printf("dep[%d]=%lld,rem[%d]=%lld\n",i,dep[i],i,rem[i]);
        if(!rem[i])continue;
        mxdep = max(mxdep,dep[i]);
        
    }
    for(int i=1;i<=n;i++){
        if(!rem[i])continue;
        if(dep[i]==mxdep){
            to_op.push_back(i);
            supd[i]=rk[(i)%m+1];
        }
        else{
            if(id[i]){
                //d[dep[i]].push_back(i);
                //printf("leaf not equal\n");
                printf("Tie\n");
                return;
            }
        }
    }
    while(mxdep--){
        //for(int i=1;i<=n;i++){
            //printf("supd[%d]=%lld\n",i,supd[i]);
        //}
        vector<int> nxt;
        for(auto u:to_op ){
            if(supd[u] != -1)supd [u] = fa[supd[u]];
            if(!vis[fa[u ]]){
                nxt.push_back(fa[u ]);
                vis[fa[u]]=1;
            }
        }
        for(auto u:nxt){
            for(auto v:g[u]){
                if(v == fa[u])continue;
                if(!supd[u])supd[u]=supd[v];
                else{
                    if(supd[v]==-1)supd[u]=-1;
                    else if(supd[v] != supd[u]){
                        supd[u]=-1;
                    }
                }
                
                
            }
        }
        to_op.clear();
        for(auto u:nxt){
            to_op.push_back(u);
        }
        
    }
    //for(int i=1;i<=n;i++){
    //        printf("supd[%d]=%lld\n",i,supd[i]);
    //    }
    if(supd[n ] == n){
        printf("Doddle\n");
    }
    else{
        printf("Tie\n");
    }
}
int main(){
    int T;
    cin >> T;
    while(T--)solve();
}