// SPDX-License-Identifier: Unlicense
// Author: Bingwu Zhang <xtex@xtexx.eu.org>
#include <bits/stdc++.h>

#define uint unsigned int
#define ull unsigned long long
#define expT(x) __builtin_expect(x, 1)
#define expF(x) __builtin_expect(x, 0)

namespace xtex
{

    uint rdu()
    {
        uint v = 0;
        char ch = getchar();
        while (!(ch >= '0' && ch <= '9'))
            ch = getchar();
        while (ch >= '0' && ch <= '9')
        {
            v = (v << 3) + (v << 1) + (ch ^ '0');
            ch = getchar();
        }
        return v;
    }

#define MAXN 100005
#define MOD 1000000007

    uint c, n, k;
    class tnode
    {
    public:
        std::set<uint> edge;
    };
    class Edge
    {
    public:
        uint u, v;
        std::set<uint> edge;
    };
    tnode rt[MAXN];
    Edge g[MAXN];

    uint sol()
    {
        n = rdu();
        k = rdu();
        if (expF(c == 18)) // 性质A
        {
            //  ui = i, vi = i + 1
            for (uint i = 1; i < n; ++i)
                rdu(), rdu();
            for (uint i = 0; i < k; ++i)
                rdu();
            return 1;
        }
        else if (expF(c >= 19 && c <= 21))
        {
            // ui = 1, vi = i + 1
            // (n-1)*(n-2)选(n-2)求选法
            // ...，忘了公式
        }
        for (uint i = 1; i < n; ++i)
        {
            uint u = rdu();
            uint v = rdu();
            rt[u].edge.insert(i);
            rt[v].edge.insert(i);
            g[i].u = u, g[i].v = v;
            g[i].edge.insert(u);
            g[i].edge.insert(v);
        }
        for (uint i = 1; i < n; ++i)
        {
            std::set<uint> enodes = std::move(g[i].edge);
            g[i].edge = std::set<uint>();
            std::set<uint> &gedg = g[i].edge;
            for (uint enode : enodes)
            {
                for (uint eedge : rt[enode].edge)
                {
                    if (eedge == i)
                        continue;
                    gedg.insert(eedge);
                }
            }
        }
        for (uint i = 0; i < k; ++i)
        {
            uint gidx = rdu();
        }
        return rand() % 5;
    }
}

int main()
{
    using namespace xtex;
    freopen("traverse.in", "r", stdin);
    freopen("traverse.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    srand(4242420361);
    c = rdu();
    uint T = rdu();
    while (T--)
    {
        uint ans = sol();
        printf("%u\n", ans);
    }
    return 0;
}
