#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 50;
using pii = pair<int, int>;
int n, m, k;
vector<int> e[N];
vector<pii> edges;
int f[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }
int siz[N], sizm[N];
int vis[N];
int du[N];
int type[N]; // 1:tree, 2:chain, 3:circle with tree, 4:only circle, 5:K_{1,3}, 6:others

bool connect(int x, int y)
{
    x = Find(x), y = Find(y);
    if (x != y)
    {
        f[y] = x;
        sizm[x] += sizm[y];
        siz[x] += siz[y];
        sizm[x]++;
        return true;
    }
    sizm[x]++;
    return false;
}

bool vis_huan[N];
vector<int> vec[N];
int cnt[10];
int ans;

vector<int> g[N];
int tot, nxt_n;
map<pii, int> mp;
int id(int u, int v)
{
    if (u > v)
        swap(u, v);
    if (!mp.count({u, v}))
        mp[{u, v}] = ++nxt_n;
    return mp[{u, v}];
}

void line_graph()
{
    mp.clear();
    for (int i = 1; i <= n; i++)
        g[i].clear(), g[i].shrink_to_fit();
    for (int i = 1; i <= tot; i++)
    {
        for (auto v : e[i])
        {
            int u = i;
            id(u, v);
            if (nxt_n >= ans)
                return;
        }
        for (int j = 0; j < e[i].size(); j++)
            for (int k = j + 1; k < e[i].size(); k++)
            {
                int u = i, v = e[i][j], v2 = e[i][k];
                int e1 = id(u, v), e2 = id(u, v2);
                
            }
    }
}

void solve()
{
    cin >> n >> m >> k;
    ans = n;
    for (int i = 1; i <= n; i++)
        e[i].clear(), du[i] = 0, siz[i] = sizm[i] = type[i] = 0, vec[i].clear();
    edges.clear();
    memset(cnt, 0, sizeof(cnt));
    iota(f + 1, f + n + 1, 1);
    fill(siz, siz + n + 1, 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        du[u]++, du[v]++;
        if (u > v)
            swap(u, v);
        edges.emplace_back(u, v);
        connect(u, v);
    }
    fill(vis, vis + n + 5, 0);
    for (int i = 1; i <= n; i++)
        vec[Find(i)].push_back(i);
    for (int i = 1; i <= n; i++)
    {
        if (!vis[Find(i)])
        {
            int fa = Find(i);
            if (sizm[fa] > siz[fa])
                type[fa] = 6;
            else if (sizm[fa] == siz[fa])
            {
                int flag = 1;
                for (auto j : vec[fa])
                {
                    if (du[j] != 2)
                        flag = 0;
                }
                if (flag)
                    type[fa] = 4;
                else
                    type[fa] = 3;
            }
            else
            {
                int flag = 1;
                for (auto j : vec[fa])
                    if (du[j] > 2)
                        flag = 0;
                if (flag)
                    type[fa] = 2;
                else if (siz[fa] == 4)
                    type[fa] = 5;
                else
                    type[fa] = 1;
            }
            cnt[type[fa]]++;
        }
        vis[Find(i)] = 1;
    }

    tot = n;
    line_graph();
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}