#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10, M = 2e5 + 10;

//链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int depth[N], f[N][31];
int dlt[N]; //差分数组

// 倍增2^k,计算k的办法
// T = log(n) / log(2) + 1;
const int T = 25;

//倍增求 a,b的最近公共祖先
void bfs(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;

    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j]) continue;
            depth[j] = depth[u] + 1;
            f[j][0] = u;
            for (int k = 1; k <= T; k++) f[j][k] = f[f[j][k - 1]][k - 1];
            q.push(j);
        }
    }
}
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = T; k >= 0; k--)
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];

    if (a == b) return a;
    for (int k = T; k >= 0; k--)
        if (f[a][k] != f[b][k])
            a = f[a][k], b = f[b][k];

    return f[a][0];
}

//前缀和
void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        dlt[u] += dlt[j];
    }
}

int main() {
    int T, n, m;
    scanf("%d", &T);
    int cc = 0;
    while (T--) {
        idx = 0;
        memset(h, -1, sizeof h);
        memset(depth, 0, sizeof depth);
        memset(dlt, 0, sizeof dlt);

        scanf("%d%d", &n, &m);

        for (int i = 1; i < n; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }
        bfs(1);

        for (int i = n; i <= m; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            //树上差分+边权(把边权记在点上)
            dlt[a]++;
            dlt[b]++;
            dlt[lca(a, b)] -= 2;
        }
        //前缀和合并差分
        dfs(1, 0);

        int res = INF;
        /*
          Q:为什么最后统计的时候 n 是从 2 开始?
          A:因为1没边的, 边差分，他这边是下放到下面的那个点上，用点来表示这个边的。
        */
        for (int i = 2; i <= n; i++) res = min(res, dlt[i] + 1);
        printf("Case #%d: %d\n", ++cc, res);
    }
}