題意：

n個(gè)學(xué)生要組成一個(gè)小組參加會(huì)議（可以不參加），
1.對(duì)于每?jī)蓚€(gè)朋友（x ，y)，如果他們倆都參加會(huì)議，該小組的友好價(jià)值將會(huì)增加 1；如果其中只有一位參加會(huì)議，則該組的友好價(jià)值將降低 1。
3.如果n個(gè)學(xué)生參加會(huì)議，對(duì)團(tuán)隊(duì)的友好價(jià)值將降低n.

題目：

Professor Alex will organize students to attend an academic conference.

Alex has n excellent students, and he decides to select some of them (possibly none) to attend the conference. They form a group. Some pairs of them are friends.

The friendly value of the group is initially 0. For each couple of friends (x,y), if both of them attend the conference, the friendly value of the group will increase 1, and if only one of them attends the conference, the friendly value of the group will decrease 1. If k students attend the conference, the friendly value of the group will decrease k.

Alex wants to make the group more friendly. Please output the maximum friendly value of the group.

Input

The first line of the input gives the number of test cases, T (1≤T≤104). T test cases follow.

For each test case, the first line contains two integers n (1≤n≤3×105) and m (1≤m≤106), where n is the number of students and m is the number of couples of friends.

Each of the following m lines contains two integers xi,yi (1≤xi,yi≤n,xi≠yi), representing student xi and student yi are friends. It guaranteed that unordered pairs (xi,yi) are distinct.

The sum of n in all test cases doesn’t exceed 106, and the sum of m in all test cases doesn’t exceed 2×106.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1), and y is the maximum friendly value of the group.

Example

Input

2
4 5
1 2
1 3
1 4
2 3
3 4
2 1
1 2

Output

Case #1: 1
Case #2: 0

分析：

1.由題意，友好價(jià)值=組群里的邊數(shù)-點(diǎn)數(shù)；
2.那么怎么求最大友好價(jià)值？由于對(duì)于每?jī)蓚€(gè)朋友（x ，y)，如果他們倆都參加會(huì)議，該小組的友好價(jià)值將會(huì)增加 1；如果其中只有一位參加會(huì)議，則該組的友好價(jià)值將降低 1，所以我們用并查集，直接找根節(jié)點(diǎn)遍歷到最后，這時(shí)就變成了一個(gè)個(gè)的組群，我們只要判斷這些組群是否參加會(huì)議即可，當(dāng)組群里的邊數(shù)-點(diǎn)數(shù)<0時(shí)，不讓其參加，反之參加即可求得。

AC代碼：

#include<bits/stdc++.h> using namespace std; const int M=3e5+10; int t,n,m,k,ans; int f[M],a[M],b[M]; int getf(int x){if(f[x]==x) return x;return f[x]=getf(f[x]); } int main(){cin>>t;k=0;while(t--){cin>>n>>m;for(int i=1;i<=n;i++){f[i]=i;a[i]=0;//記錄邊，起始邊個(gè)數(shù)為零。b[i]=1;//記錄點(diǎn)，原始本身就為一個(gè)點(diǎn)。}for(int i=1;i<=m;i++){int t1,t2;scanf("%d%d",&t1,&t2);int u=getf(t1);int v=getf(t2);if(u==v) a[u]++;else {f[v]=u;a[u]+=a[v]+1;//因?yàn)樽罱K怕判斷的根節(jié)點(diǎn)判組群，所以記錄邊和點(diǎn)只需要在根節(jié)點(diǎn)上即可。b[u]+=b[v];}}ans=0;for(int i=1;i<=n;i++){if(i==f[i]&&a[i]-b[i]>0)ans+=a[i]-b[i];}printf("Case #%d: %d\n",++k,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Friendly Group Gym - 102769F 2020（并查集）ccpc秦皇岛分站赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。