#include "testlib.h"
#include <string>
#include <vector>
#include <set>
#include <numeric>

using namespace std;

vector<int> pr, sz;

void is_tree(int n, vector<pair<int, int>> edges) {
    pr.assign(n, 0);
    iota(pr.begin(), pr.end(), 0);
    sz.assign(n, 1);
    for (auto el: edges) {
        int a = el.first;
        int b = el.second;
        while (a != pr[a]) a = pr[a];
        while (b != pr[b]) b = pr[b];
        ensuref(a != b, "not tree");
        if (sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        pr[b] = a;
    }
}

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int t = inf.readInt(1, 10000, "t");
    inf.readEoln();
    for (int _ = 1; _ <= t; _++) {
        setTestCase(_);
        int n = inf.readInt(2, 100'000, "n");
        inf.readSpace();
        int k = inf.readInt(2, 2 * n, "k");
        inf.readEoln();
        vector<pair<int, int>> edges1, edges2;
        for (int i = 0; i + 1 < n; i++) {
            int a = inf.readInt(1, n, "a_i");
            inf.readSpace();
            int b = inf.readInt(1, n, "b_i");
            inf.readEoln();
            a--, b--;
            edges1.push_back({a, b});
        }
        for (int i = 0; i + 1 < n; i++) {
            int a = inf.readInt(1, n, "a_i");
            inf.readSpace();
            int b = inf.readInt(1, n, "b_i");
            inf.readEoln();
            a--, b--;
            edges2.push_back({a, b});
        }
        is_tree(n, edges1);
        is_tree(n, edges2);
    }
    inf.readEof();
}
