#include<bits/stdc++.h>

 #define in(a) scanf("%d",&a)

 using namespace std;

 struct nod

 {

     int v,next;

 }side[];

 int head[],cnt,index,fri[];

 void add(int u,int v)

 {

     side[cnt].v=v;

     side[cnt].next=head[u];

     head[u]=cnt++;

     fri[u]++;

 }

 int scc[],dfn[],low[],ins[],vis[],stac[],tail;

 void tarjan(int cur)

 {

     dfn[cur]=low[cur]=index++;

     ins[cur]=;

     vis[cur]=;

     stac[tail++]=cur;

     for(int i=head[cur];i!=-;i=side[i].next)

     {

         int c=side[i].v;

         if(!vis[c])

         {

             tarjan(c);

             low[cur]=min(low[cur],low[c]);

         }

         else if(ins[c])

             low[cur]=min(low[cur],dfn[c]);

     }

     if(dfn[cur]==low[cur])

     {

         cnt++;

         int v;

         do

         {

             v=stac[tail-];

             scc[v]=cnt;

             ins[v]=;

             tail--;

         }while(v!=cur);

     }

 }

 int main()

 {

     int N;

     in(N);

     while(N--)

     {

         memset(head,-,sizeof(head));

         memset(ins,,sizeof(ins));

         memset(vis,,sizeof(vis));

         memset(fri,,sizeof(fri));

         int n,m,k,x,y;

         in(n);in(m);in(k);

         cnt=;

         for(int i=;i<m;i++)

         {

             in(x);in(y);

             add(x,y);add(y,x);

         }

         index=;tail=;cnt=;

         int maxn=;

         for(int i=;i<n;i++)

             {

                 if(!vis[i])

                 tarjan(i);

                 maxn=max(maxn,fri[i]);

             }

         if(maxn+cnt-+k>n-)

             printf("%d\n",n-);

         else

             printf("%d\n",maxn+cnt-+k);

     }

     return ;

 }