
// топ, топ, топ

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define int long long
const int maxn = 5e5+10, maxnn = 2e3+10, maxk = 5e5+10, inf = 1e18;
int cost[maxnn][maxnn], n, m, k;
std::vector < int > v[maxn];
std::queue < int > q[3];
std::pair < int, int > p[maxk];
int sparse[20][maxn];
std::vector < int > tour;

struct Edge
{
    int from, to;
} edge[maxn];

int dist[maxn];
int bfs(int from, int to)
{
    // std::cout << "bfs: " << from << ' ' << to << '\n';
    std::fill(dist+1, dist+1+n, 5);
    while(!q[0].empty()) q[0].pop();
    while(!q[1].empty()) q[1].pop();
    while(!q[2].empty()) q[2].pop();

    q[0].push(from);
    dist[from] = 0;
    for (int i = 0 ; i < 3 ; ++i)
    {
        while (!q[i].empty())
        {
            int top = q[i].front();
            // std::cout << "here: " << top << ' ' << i << '\n';
            q[i].pop();
            if (top == to) return i;
            if (dist[top] < i) continue;

            for (int j : v[top])
            {
                // if (j == to && cost[top][j] == 0) return i;
                if (dist[j] > i + cost[top][j])
                {
                    dist[j] = i + cost[top][j];
                    q[dist[j]].push(j);
                }
            }
        }
    }
}

int check()
{
    int ans = 0;
    for (int i = 1 ; i <= k ; ++i)
        ans += bfs(p[i].first, p[i].second);
    return ans;

}

void solve()
{
    int ans = -1, ix1, ix2;
    for (int i = 1 ; i <= m ; ++i)
    {
        cost[edge[i].from][edge[i].to] = 1;
        cost[edge[i].to][edge[i].from] = 1;
        for (int j = i+1 ; j <= m ; ++j)
        {
            cost[edge[j].from][edge[j].to] = 1;
            cost[edge[j].to][edge[j].from] = 1;
            int curr = check();
            if (ans < curr)
            {
                ans = curr;
                ix1 = i;
                ix2 = j;
            }
            cost[edge[j].from][edge[j].to] = 0;
            cost[edge[j].to][edge[j].from] = 0;
        }
        cost[edge[i].from][edge[i].to] = 0;
        cost[edge[i].to][edge[i].from] = 0;
    }
    std::cout << ans << '\n';
    std::cout << edge[ix1].from << ' ' << edge[ix1].to <<'\n';
    std::cout << edge[ix2].from << ' ' << edge[ix2].to <<'\n';

}

int depth[maxn], parent[maxn], edge_cost[maxn], in[maxn], out[maxn], add[maxn];
void dfs_5(int x, int p)
{
    depth[x] = depth[p] + 1;
    tour.push_back(x);
    in[x] = tour.size()-1;
    for (int i : v[x])
    {
        if (i == p) continue;
        dfs_5(i, x);
        tour.push_back(x);
    }
    out[x] = tour.size()-1;
}

int cmp(int x, int y)
{
    if (depth[x] < depth[y]) return x;
    return y;
}

int getlog[2*maxn];
void build_rmq()
{
    for (int i = 1 ; i <= tour.size()-1 ; ++i) sparse[0][i] = tour[i];
    for (int log = 1 ; (1 << log) <= tour.size()-1 ; ++log)
        for (int i = 1 ; i + (1 << log) - 1 <= tour.size()-1 ; ++i)
            sparse[log][i] = cmp(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);

    getlog[0] = 1;
    for (int i = 1 ; i <= tour.size() ; ++i)
    {
        getlog[i] = getlog[i-1];
        if ((1 << getlog[i]+1) < i) ++getlog[i];
    }

}

int find_lca(int x, int y)
{
    if (in[x] > in[y]) std::swap(x, y);
    int log = getlog[in[y] - in[x] + 1];
    return cmp(sparse[log][in[x]], sparse[log][in[y] - (1 << log) + 1]);
}

int find_cost(int x, int p)
{
    parent[x] = p;
    edge_cost[x] = add[x];
    for (int i : v[x])
    {
        if (i == p) continue;
        edge_cost[x] += find_cost(i, x);
    }
    return edge_cost[x];
}

int perm[maxn];
bool cmp2(int x, int y)
{
    if (edge_cost[x] > edge_cost[y]) return 1;
    return 0;
}

void solve_5()
{
    tour.push_back(0);
    dfs_5(1, 0);
    build_rmq();

    for (int i = 1 ; i <= k ; ++i)
    {
        ++add[p[i].first];
        ++add[p[i].second];
        // std::cout << "lca of: "<< p[i].first << ' ' << p[i].second << " = " << find_lca(p[i].first, p[i].second) << '\n';
        add[find_lca(p[i].first, p[i].second)] -= 2;
    }

    // std::cout << "add:\n";
    // for (int i = 1 ; i <= n ; ++i)
    //     std::cout << i << " = "<< add[i] << '\n';

    find_cost(1, 0);
    // for (int i = 2 ; i <= n ; ++i)
    //    std::cout << "passing: " << parent[i] << ' ' << i << " = " << edge_cost[i] << '\n';

    for (int i = 1 ; i < n ; ++i) perm[i] = i+1;
    std::sort(perm+1, perm+n, cmp2);
    std::cout << edge_cost[perm[1]] + edge_cost[perm[2]] << '\n';
    std::cout << parent[perm[1]] << ' ' << perm[1] <<'\n';
    std::cout << parent[perm[2]] << ' ' << perm[2] <<'\n';

}

void read()
{
    int x, y, d;
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> edge[i].from >> edge[i].to;
        v[edge[i].from].push_back(edge[i].to);
        v[edge[i].to].push_back(edge[i].from);
    }

    std::cin >> k;
    for (int i = 1 ; i <= k ; ++i) std::cin >> p[i].first >> p[i].second;

}

void reset()
{
    tour.clear();
    std::fill(add+1, add+1+n, 0);
    std::fill(edge_cost+1, edge_cost+1+n, 0);
    std::fill(in+1, in+1+n, 0);
    std::fill(depth+1, depth+1+n, 0);
    for (int i = 1 ; i <= n ; ++i) v[i].clear();
}

void fast_io()
{
    std::ios_base :: sync_with_stdio(0);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int tests, groups;
signed main()
{
    fast_io();
    std::cin >> tests >> groups;

    while (tests--)
    {
        reset();
        read();
        if (groups != 5) solve();
        else solve_5();
    }

    return 0;

}

/**
1 5
6 5
1 2
2 3
2 4
4 5
4 6
5
1 6
5 3
2 5
5 6
4 3
*/
