1 #include<bits/stdc++.h> 2 #define in(a) scanf("%d",&a) 3 using namespace std; 4 5 struct nod 6 { 7 int v,next; 8 }side[405555]; 9 10 int head[200005],cnt,index,fri[200005]; 11 12 void add(int u,int v) 13 { 14 side[cnt].v=v; 15 side[cnt].next=head[u]; 16 head[u]=cnt++; 17 fri[u]++; 18 19 } 20 21 int scc[200005],dfn[200005],low[2000005],ins[200005],vis[200005],stac[200005],tail; 22 23 void tarjan(int cur) 24 { 25 dfn[cur]=low[cur]=index++; 26 ins[cur]=1; 27 vis[cur]=1; 28 stac[tail++]=cur; 29 for(int i=head[cur];i!=-1;i=side[i].next) 30 { 31 int c=side[i].v; 32 if(!vis[c]) 33 { 34 tarjan(c); 35 low[cur]=min(low[cur],low[c]); 36 } 37 else if(ins[c]) 38 low[cur]=min(low[cur],dfn[c]); 39 } 40 if(dfn[cur]==low[cur]) 41 { 42 cnt++; 43 int v; 44 do 45 { 46 v=stac[tail-1]; 47 scc[v]=cnt; 48 ins[v]=0; 49 tail--; 50 }while(v!=cur); 51 } 52 } 53 54 int main() 55 { 56 int N; 57 in(N); 58 while(N--) 59 { 60 memset(head,-1,sizeof(head)); 61 memset(ins,0,sizeof(ins)); 62 memset(vis,0,sizeof(vis)); 63 memset(fri,0,sizeof(fri)); 64 int n,m,k,x,y; 65 in(n);in(m);in(k); 66 cnt=0; 67 for(int i=0;i<m;i++) 68 { 69 in(x);in(y); 70 add(x,y);add(y,x); 71 } 72 index=0;tail=0;cnt=0; 73 int maxn=0; 74 for(int i=0;i<n;i++) 75 { 76 if(!vis[i]) 77 tarjan(i); 78 maxn=max(maxn,fri[i]); 79 } 80 if(maxn+cnt-1+k>n-1) 81 printf("%d ",n-1); 82 else 83 printf("%d ",maxn+cnt-1+k); 84 85 86 } 87 return 0; 88 }