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

int MINT = 1;
int MAXT = 10'000;
int MINN = 3;
int MAXN = 1'000'000'000;
int MINM = 0;
int MAXM = 200'000;
int MINK = 2;
int MAXK = 1'000'000;

int SUMM = 200'000;

int main(int argc, char** argv) {
	registerValidation(argc, argv);
	
	int t = inf.readInt(MINT, MAXT, "t");
    inf.readEoln();
    
    int sum_m = 0;
	
	for (int q = 1; q <= t; ++q) {
	    setTestCase(q);
    	int n = inf.readInt(MINN, MAXN, "n");
    	inf.readSpace();
    	int m = inf.readInt(MINM, MAXM, "m");
    	inf.readSpace();
    	int k = inf.readInt(MINK, MAXK, "k");
    	inf.readEoln();
    	
    	sum_m += m;
        ensuref(sum_m <= SUMM, "sum of m is too large: %d > %d", sum_m, SUMM);
    	
    	vector<int> u(m), v(m);
    	for (int i = 0; i < m; i++) {
            u[i] = inf.readInt(1, n, "u_" + to_string(i + 1)) - 1;
            inf.readSpace();
            v[i] = inf.readInt(u[i] + 1, n, "v_" + to_string(i + 1)) - 1;
            inf.readEoln();
    	}
    	
    	set<pair<int, int>> s;
    	vector<pair<int, int>> g;
    	for (int i = 0; i < m; i++) {
            ensuref(u[i] != v[i], "edge %d is loop", i + 1);
            if (u[i] > v[i]) {
                swap(u[i], v[i]);
            }
            ensuref(u[i] + 1 != v[i], "edge %d has length 1", i + 1);
            ensuref(u[i] != 0 || v[i] != n - 1, "edge %d has length 1", i + 1);
            ensuref(s.find({u[i], v[i]}) == s.end(), "edge %d is duplicate", i + 1);
            s.insert({u[i], v[i]});
            g.push_back({u[i], v[i]});
            g.push_back({v[i], u[i]});
    	}
    	
        sort(g.begin(), g.end(), [&](pair<int, int> a, pair<int, int> b) {
            if (a.first != b.first) {
                return a.first < b.first;
            }
            if (a.second < a.first) {
                if (b.second > b.first) {
                    return true;
                }
                return a.second > b.second;
            }
            if (b.second < b.first) {
                return false;
            }
            return a.second > b.second;
    	});
    
    	vector<pair<int, int>> st;
    	for (pair<int, int> e : g) {
            if (e.first < e.second) {
                st.push_back(e);
                continue;
            }
            assert(!st.empty());
            ensuref(st.back() == pair(e.second, e.first), "edges (%d; %d) and (%d, %d) intersect", st.back().first + 1, st.back().second + 1, e.second + 1, e.first + 1);
            st.pop_back();
    	}
    	assert(st.empty());
	}
	inf.readEof();

	return 0;
}