#include <bits/stdc++.h>

using namespace std;

#define iter(v) v.begin(), v.end()
#define SZ(v) int(v.size())
#define pb emplace_back
#define ff first
#define ss second
#define fs ff
#define sc ss

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#ifdef zisk
void debug(){cerr << "\n";}
template<class T, class ... U>
void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

template<class A, class B>
ostream &operator<<(ostream& o, pair<A, B> p) {
	return o << '(' << p.ff << ',' << p.ss << ')';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n,m,k;
		cin >> n >> m >> k;
		vector<vector<pii> > v(n);
		for(int i=0;i<m;i++){
			int a,b;
			cin >> a >> b;
			a--;
			b--;
			v[a].push_back({b,i});
			v[b].push_back({a,i});
		}
		k--;
		if(k==0){
			cout << n << '\n';
			continue;
		}
		ll w2=0;
		for(int i=0;i<n;i++){
			w2+=1ll*(v[i].size())*(v[i].size()-1)/2;
		}
		if(w2>2*n){
			cout << n << '\n';
			continue;
		}
		int wwww=n;
		int ans=1e9;
		vector<vector<pii> > v3(m);
		int cnt2=0;
		for(int i=0;i<n;i++){
			for(auto h:v[i]){
				for(auto p:v[i]){
					if(h!=p){
						v3[h.sc].push_back({p.sc,cnt2});
						cnt2++;
					}
				}
			}
		}
		v.swap(v3);
		n=v.size();
		ans=min(ans,n);
		m=cnt2;
		k--;
		int mxd=0;
		for(int i=0;i<n;i++){
			mxd=max(mxd,(int)v[i].size());
		}
		if(mxd<=2){
			vector<int> vis(n);
			int gg=1;
			auto dfs=[&](auto zck,int r,int f)-> pii{
				vis[r]=gg;
				gg++;
				//debug(r,f);
				int a=1,b=0;
				for(auto h:v[r]){
					if(!vis[h.fs]){
						auto z=zck(zck,h.fs,r);
						a+=z.fs;
						b+=z.sc;
						b++;
					}
					else if(vis[h.fs]>vis[r]){
						b++;
					}
				}
				return {a,b};
			};
			//debug(n);
			int sum=0;
			for(int i=0;i<n;i++){
				if(!vis[i]){
					auto a=dfs(dfs,i,i);
					debug(a.fs,a.sc);
					if(a.sc==a.fs){
						sum+=a.fs;
						continue;
					}
					sum+=max(0,a.fs-k);
				}
			}
			ans=min(ans,sum);
			cout << ans << "\n";
			continue;
		}
		int s=0;
		while(1){
			if(k<=0){
				break;
			}
			ans=min(ans,m);
			k--;
			vector<vector<pii> > v2(m);
			ll w=0;
			for(int i=0;i<n;i++){
				w+=1ll*v[i].size()*(v[i].size()-1)/2;	
			}
			if(w>2*n){
				break;
			}
			if(w>=ans){
				break;
			}
			int cnt=0;
			for(int i=0;i<n;i++){
				for(auto h:v[i]){
					for(auto p:v[i]){
						if(h!=p){
							v2[h.sc].push_back({p.sc,cnt});
							cnt++;
						}
					}
				}
			}
			v.swap(v2);
			n=v.size();
			ans=min(ans,n);
			m=cnt;
			s=1;
		}
		cout << min(ans,wwww) << "\n";
	}

}