// 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
Ly8gaW9zdHJlYW0gaXMgdG9vIG1haW5zdHJlYW0KI2luY2x1ZGUgPGNzdGRpbz4KLy8gYml0Y2ggcGxlYXNlCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8aW9tYW5pcD4KI2RlZmluZSBkaWJzIHJlc2VydmUKI2RlZmluZSBPVkVSOTAwMCAxMjM0NTY3ODkwCiNkZWZpbmUgQUxMX1RIRShDQUtFLExJRSkgZm9yKGF1dG8gTElFID1DQUtFLmJlZ2luKCk7IExJRSAhPSBDQUtFLmVuZCgpOyBMSUUrKykKI2RlZmluZSB0aXNpYyA0NwojZGVmaW5lIHNvY2xvc2UgMWUtOAojZGVmaW5lIGNob2NvbGF0ZSB3aW4KLy8gc28gbXVjaCBjaG9jb2xhdGUKI2RlZmluZSBwYXRrYW4gOQojZGVmaW5lIGZmIGZpcnN0CiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgYWJzKHgpICgoeCA8IDApPy0oeCk6eCkKI2RlZmluZSB1aW50IHVuc2lnbmVkIGludAojZGVmaW5lIGRibCBsb25nIGRvdWJsZQp1c2luZyBuYW1lc3BhY2Ugc3RkOwovLyBteWxpdHRsZWRvZ2UKCnZvaWQgY29uc3RJKGludCBSLCB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJnNvbiwgdmVjdG9yPCBwYWlyPGludCxpbnQ+ID4gJkksIHZlY3RvcjxpbnQ+ICZEKSB7CglJW1JdLnNzID1JW1JdLmZmKzE7CglBTExfVEhFKHNvbltSXSxpdCkgewoJCUlbKml0XS5mZiA9SVtSXS5zczsKCQlEW0lbKml0XS5mZl0gPURbSVtSXS5mZl0rMTsKCQljb25zdEkoKml0LHNvbixJLEQpOwoJCUlbUl0uc3MgPUlbKml0XS5zczt9Cgl9CgpzdHJ1Y3Qgbm9kZSB7CglpbnQgc29uWzJdOwoJaW50IHosayxtb2Q7CglwYWlyPGludCxpbnQ+IHZhbDsKCX07CgpzdHJ1Y3QgaW50ZXJ2YWxhYyB7Cgl2ZWN0b3I8bm9kZT4gVDsKCQoJdm9pZCBjb25zdEkoaW50IGFrdCwgdmVjdG9yPGludD4gJkEpIHsKCQlub2RlIG4gPVRbYWt0XTsKCQlpZihuLnogPT0gbi5rLTEpIHsKCQkJVFtha3RdLnZhbCA9bWFrZV9wYWlyKEFbbi56XSxuLnopOwoJCQlyZXR1cm47fQoJCWZvcihpbnQgaSA9MDsgaSA8IDI7IGkrKykgewoJCQlpZihpID09IDApIG4uayA9KG4ueituLmspLzI7CgkJCWVsc2Uge24ueiA9bi5rOyBuLmsgPVRbYWt0XS5rO30KCQkJVFtha3RdLnNvbltpXSA9VC5zaXplKCk7CgkJCVQucHVzaF9iYWNrKG4pOwoJCQljb25zdEkoVFtha3RdLnNvbltpXSxBKTt9CgkJVFtha3RdLnZhbCA9bWF4KFRbVFtha3RdLnNvblswXV0udmFsLFRbVFtha3RdLnNvblsxXV0udmFsKTt9CgkKCWludGVydmFsYWMoaW50IE4sIHZlY3RvcjxpbnQ+ICZBKSB7CgkJbm9kZSBuOwoJCW4ubW9kID1uLnogPTA7CgkJbi5rID1OOwoJCW4uc29uWzBdID1uLnNvblsxXSA9LTE7CgkJbi52YWwgPW1ha2VfcGFpcigwLDApOwoJCVQuZGlicyhOKjIrdGlzaWMpOwoJCVQucmVzaXplKDEsbik7CgkJY29uc3RJKDAsQSk7fQoJCgl2b2lkIHVwZChpbnQgYWt0KSB7CgkJbm9kZSBuID1UW2FrdF07CgkJaWYobi5tb2QgPT0gMCkgcmV0dXJuOwoJCVRbYWt0XS52YWwuZmYgKz1uLm1vZDsKCQlmb3IoaW50IGkgPTA7IGkgPCAyOyBpKyspIGlmKG4uc29uW2ldID49IDApCgkJCVRbbi5zb25baV1dLm1vZCArPW4ubW9kOwoJCVRbYWt0XS5tb2QgPTA7fQoJCgl2b2lkIHB1dChpbnQgYWt0LCBpbnQgemFjLCBpbnQga29uLCBpbnQgdmFsKSB7CgkJdXBkKGFrdCk7CgkJbm9kZSBuID1UW2FrdF07CgkJaWYobi5rIDw9IHphYyB8fCBrb24gPD0gbi56KSByZXR1cm47CgkJaWYobi56ID09IHphYyAmJiBrb24gPT0gbi5rKSB7CgkJCVRbYWt0XS5tb2QgKz12YWw7CgkJCXVwZChha3QpOwoJCQlyZXR1cm47fQoJCXB1dChuLnNvblswXSx6YWMsbWluKGtvbiwobi56K24uaykvMiksdmFsKTsKCQlwdXQobi5zb25bMV0sbWF4KHphYywobi56K24uaykvMiksa29uLHZhbCk7CgkJdXBkKG4uc29uWzBdKTsKCQl1cGQobi5zb25bMV0pOwoJCVRbYWt0XS52YWwgPW1heChUW24uc29uWzBdXS52YWwsVFtuLnNvblsxXV0udmFsKTt9CgoJcGFpcjxpbnQsaW50PiBnZXQoKSB7CgkJdXBkKDApOwoJCXJldHVybiBUWzBdLnZhbDt9Cgl9OwoKaW50IG1haW4oKSB7CgljaW4uc3luY193aXRoX3N0ZGlvKDApOwoJY2luLnRpZSgwKTsKCWludCBUOwoJY2luID4+IFQ7Cglmb3IoaW50IHQgPTA7IHQgPCBUOyB0KyspIHsKCQlpbnQgTixNLEs7CgkJY2luID4+IE4gPj4gTSA+PiBLOwoJCXZlY3RvcjwgdmVjdG9yPGludD4gPiBHKE4pLCBzb24oTisxKTsKCQl2ZWN0b3I8aW50PiBEKE4pOwoJCWZvcihpbnQgaSA9MDsgaSA8IE07IGkrKykgewoJCQlpbnQgYSxiOwoJCQljaW4gPj4gYSA+PiBiOwoJCQlHWy0tYV0ucHVzaF9iYWNrKC0tYik7CgkJCUdbYl0ucHVzaF9iYWNrKGEpOwoJCQlEW2FdKyssIERbYl0rKzt9CgoJCXF1ZXVlPGludD4gcTsKCQl2ZWN0b3I8aW50PiBwYXIoTisxLC0xKTsKCQlmb3IoaW50IGkgPTA7IGkgPCBOOyBpKyspIGlmKERbaV0gPT0gMSkgcS5wdXNoKGkpLCBwYXJbaV0gPS0yOwoJCXdoaWxlKCFxLmVtcHR5KCkpIHsKCQkJQUxMX1RIRShHW3EuZnJvbnQoKV0saXQpIHsKCQkJCURbKml0XS0tOwoJCQkJaWYoRFsqaXRdID09IDEpIHEucHVzaCgqaXQpLCBwYXJbKml0XSA9LTI7CgkJCQlpZihEWyppdF0gPCAxKSBwYXJbKml0XSA9cS5mcm9udCgpLCBzb25bcS5mcm9udCgpXS5wdXNoX2JhY2soKml0KTt9CgkJCXEucG9wKCk7fQoJCWZvcihpbnQgaSA9MDsgaSA8IE47IGkrKykgaWYocGFyW2ldID09IC0yKSB7CgkJCXNvbltOXS5wdXNoX2JhY2soaSk7CgkJCXBhcltpXSA9Tjt9CgkJCgkJdmVjdG9yPCBwYWlyPGludCxpbnQ+ID4gSShOKzEsbWFrZV9wYWlyKDAsMCkpOwoJCXZlY3RvcjxpbnQ+IGRlcChOKzEsMCksIHZpcyhOKzEsMSk7CgkJY29uc3RJKE4sc29uLEksZGVwKTsKCQl2ZWN0b3I8aW50PiBJaShOKzEpOwoJCWZvcihpbnQgaSA9MDsgaSA8PSBOOyBpKyspIGlmKElbaV0uc3MgIT0gSVtpXS5mZikgSWlbSVtpXS5mZl0gPWk7CgkJdmlzW05dID0wOwoJCWZvcihpbnQgaSA9MDsgaSA8IE47IGkrKykgaWYocGFyW2ldID09IC0xKSB2aXNbaV0gPTA7CgkJCgkJaW50ZXJ2YWxhYyBJbihOKzEsZGVwKTsKCQlmb3IoaW50IGsgPTA7IGsgPCBLOyBrKyspIHsKCQkJcGFpcjxpbnQsaW50PiBueHRMID1Jbi5nZXQoKTsKCQkJaW50IGFrdCA9SWlbbnh0TC5zc107CgkJCXdoaWxlKHZpc1tha3RdKSB7CgkJCQl2aXNbYWt0XSA9MDsKCQkJCUluLnB1dCgwLElbYWt0XS5mZixJW2FrdF0uc3MsLTEpOwoJCQkJYWt0ID1wYXJbYWt0XTt9CgkJCX0KCQkKCQlpbnQgYW5zID0wOwoJCWZvcihpbnQgaSA9MDsgaSA8IE47IGkrKykgaWYodmlzW2ldKSBhbnMrKzsKCQljb3V0IDw8IGFucyA8PCAiXG4iO30KCXJldHVybiAwO30KCi8vIGxvb2sgYXQgbXkgY29kZQovLyBteSBjb2RlIGlzIGFtYXppbmc=