1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<vector>  5 #include<queue>  6 #include<stack>  7 #define mt(a,b) memset(a,b,sizeof(a))  8 using namespace std;  9 typedef long long LL; 10 class Tarjan_U { ///无向图连通分量缩点o(MV+ME) 11     typedef int typec;///边权的类型 12     static const int ME=200010;///边的个数 13     static const int MV=10010;///点的个数 14     struct Q{ 15         int u,v; 16         typec w; 17     }now; 18     vector<Q> qiao; 19     int Bcnt,Index,num[MV],dfn[MV],low[MV],belong[MV]; 20     stack<int> s; 21     void addqiao(int u,int v,typec w){ 22         now.u=u; 23         now.v=v; 24         now.w=w; 25         qiao.push_back(now); 26     } 27     void tarjan(int u) { 28         s.push(u); 29         dfn[u]=low[u]=++Index; 30         int v; 31         for (int i=g.head[u]; ~i; i=g.e[i].next) { 32             if(g.e[i].vis)continue; 33             g.e[i].vis=g.e[i^1].vis=true; 34             v=g.e[i].v; 35             if (!dfn[v]) { 36                 tarjan(v); 37                 low[u]=min(low[u],low[v]); 38                 if(dfn[u]<low[v]) 39                     addqiao(u,v,g.e[i].w); 40             } else low[u]=min(low[u],dfn[v]); 41         } 42         if(dfn[u]==low[u]) { 43             Bcnt++; 44             do { 45                 v=s.top(); 46                 s.pop(); 47                 belong[v]=Bcnt; 48                 num[Bcnt]++; 49             } while(v!=u); 50         } 51     } 52 public: 53     struct G { 54         struct E { 55             int v,next; 56             bool vis; 57             typec w; 58         } e[ME]; 59         int le,head[MV]; 60         void init() { 61             le=0; 62             mt(head,-1); 63         } 64         void add(int u,int v,typec w) { 65             e[le].vis=false; 66             e[le].v=v; 67             e[le].w=w; 68             e[le].next=head[u]; 69             head[u]=le++; 70         } 71     } g; 72     void init() { 73         g.init(); 74         Index=Bcnt=0; 75         mt(num,0); 76         mt(dfn,0); 77         mt(low,0); 78         qiao.clear(); 79         while(!s.empty()) s.pop(); 80     } 81     void add(int u,int v,typec w) {///双向边 82         g.add(u,v,w); 83         g.add(v,u,w); 84     } 85     void solve(int n) {///传入点数，点下标1开始 86         for(int i=1; i<=n; i++) { 87             if(!dfn[i]) { 88                 tarjan(i); 89             } 90         } 91     } 92     int getbcnt() {///强连通分量的个数 93         return Bcnt; 94     } 95     int getbelong(int id) {///属于哪个分量，分量下标1开始 96         return belong[id]; 97     } 98     int getnum(int id) {///某个分量的点的个数 99         return num[id];100     }101 } T;102 const int M=1e5+10;103 bool vis[M],need[M];104 queue<int> q;105 int bfs(int s) {106     vis[s]=true;107     while(!q.empty()) q.pop();108     q.push(s);109     int res=0;110     while(!q.empty()) {111         int u=q.front();112         q.pop();113         res++;114         for(int i=T.g.head[u]; ~i; i=T.g.e[i].next) {115             int v=T.g.e[i].v;116             if(!vis[v]) {117                 vis[v]=true;118                 q.push(v);119             }120         }121     }122     return res;123 }124 int main() {125     int t,n,m;126     while(~scanf("%d",&t)) {127         int cas=1;128         while(t--) {129             scanf("%d%d",&n,&m);130             T.init();131             while(m--) {132                 int u,v;133                 scanf("%d%d",&u,&v);134                 T.add(u,v,1);135             }136             T.solve(n);137             mt(need,0);138             for(int i=1; i<=T.getbcnt(); i++) {139                 if(T.getnum(i)>1) need[i]=true;140             }141             mt(vis,0);142             for(int i=1; i<=n; i++) {143                 if(need[T.getbelong(i)]) {144                     vis[i]=true;145                 }146             }147             LL ans=0;148             for(int i=1; i<=n; i++) {149                 if(!vis[i]) {150                     LL dian=bfs(i);151                     ans+=dian*(dian-1)/2;152                 }153             }154             printf("Case #%d: %lld\n",cas++,ans);155         }156     }157     return 0;158 }159 /**160 4161 7 6162 1 2163 1 3164 2 4165 3 4166 4 5167 5 6168 169 170 5 4171 1 2172 2 3173 2 4174 4 5175 176 177 4 4178 1 2179 2 3180 3 4181 4 1182 183 184 8 8185 1 2186 2 3187 2 4188 2 5189 3 4190 5 6191 6 7192 6 8193 194 195 Case #1: 1196 Case #2: 10197 Case #3: 0198 Case #4: 6199 200 */