// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
using namespace std;
// mylittledoge

void constI(int R, vector< vector<int> > &son, vector< pair<int,int> > &I, vector<int> &D) {
	I[R].ss =I[R].ff+1;
	ALL_THE(son[R],it) {
		I[*it].ff =I[R].ss;
		D[I[*it].ff] =D[I[R].ff]+1;
		constI(*it,son,I,D);
		I[R].ss =I[*it].ss;}
	}

struct node {
	int son[2];
	int z,k,mod;
	pair<int,int> val;
	};

struct intervalac {
	vector<node> T;
	
	void constI(int akt, vector<int> &A) {
		node n =T[akt];
		if(n.z == n.k-1) {
			T[akt].val =make_pair(A[n.z],n.z);
			return;}
		for(int i =0; i < 2; i++) {
			if(i == 0) n.k =(n.z+n.k)/2;
			else {n.z =n.k; n.k =T[akt].k;}
			T[akt].son[i] =T.size();
			T.push_back(n);
			constI(T[akt].son[i],A);}
		T[akt].val =max(T[T[akt].son[0]].val,T[T[akt].son[1]].val);}
	
	intervalac(int N, vector<int> &A) {
		node n;
		n.mod =n.z =0;
		n.k =N;
		n.son[0] =n.son[1] =-1;
		n.val =make_pair(0,0);
		T.dibs(N*2+tisic);
		T.resize(1,n);
		constI(0,A);}
	
	void upd(int akt) {
		node n =T[akt];
		if(n.mod == 0) return;
		T[akt].val.ff +=n.mod;
		for(int i =0; i < 2; i++) if(n.son[i] >= 0)
			T[n.son[i]].mod +=n.mod;
		T[akt].mod =0;}
	
	void put(int akt, int zac, int kon, int val) {
		upd(akt);
		node n =T[akt];
		if(n.k <= zac || kon <= n.z) return;
		if(n.z == zac && kon == n.k) {
			T[akt].mod +=val;
			upd(akt);
			return;}
		put(n.son[0],zac,min(kon,(n.z+n.k)/2),val);
		put(n.son[1],max(zac,(n.z+n.k)/2),kon,val);
		upd(n.son[0]);
		upd(n.son[1]);
		T[akt].val =max(T[n.son[0]].val,T[n.son[1]].val);}

	pair<int,int> get() {
		upd(0);
		return T[0].val;}
	};

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for(int t =0; t < T; t++) {
		int N,M,K;
		cin >> N >> M >> K;
		vector< vector<int> > G(N), son(N+1);
		vector<int> D(N);
		for(int i =0; i < M; i++) {
			int a,b;
			cin >> a >> b;
			G[--a].push_back(--b);
			G[b].push_back(a);
			D[a]++, D[b]++;}

		queue<int> q;
		vector<int> par(N+1,-1);
		for(int i =0; i < N; i++) if(D[i] == 1) q.push(i), par[i] =-2;
		while(!q.empty()) {
			ALL_THE(G[q.front()],it) {
				D[*it]--;
				if(D[*it] == 1) q.push(*it), par[*it] =-2;
				if(D[*it] < 1) par[*it] =q.front(), son[q.front()].push_back(*it);}
			q.pop();}
		for(int i =0; i < N; i++) if(par[i] == -2) {
			son[N].push_back(i);
			par[i] =N;}
		
		vector< pair<int,int> > I(N+1,make_pair(0,0));
		vector<int> dep(N+1,0), vis(N+1,1);
		constI(N,son,I,dep);
		vector<int> Ii(N+1);
		for(int i =0; i <= N; i++) if(I[i].ss != I[i].ff) Ii[I[i].ff] =i;
		vis[N] =0;
		for(int i =0; i < N; i++) if(par[i] == -1) vis[i] =0;
		
		intervalac In(N+1,dep);
		for(int k =0; k < K; k++) {
			pair<int,int> nxtL =In.get();
			int akt =Ii[nxtL.ss];
			while(vis[akt]) {
				vis[akt] =0;
				In.put(0,I[akt].ff,I[akt].ss,-1);
				akt =par[akt];}
			}
		
		int ans =0;
		for(int i =0; i < N; i++) if(vis[i]) ans++;
		cout << ans << "\n";}
	return 0;}

// look at my code
// my code is amazing