// link: http://lightoj.com/volume_showproblem.php?problem=1063 // tuto: http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ /**************************************************************** ▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ █▀ ███ ███ ███ ▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀ ▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄ ███ ███ ███ ███ ███ ███ ███ ██▄ ███ ███ ███ ███ ▄█ ███ ███ ███ ███ ███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀ ****************************************************************/ #include<bits/stdc++.h> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) FOR(i, 0, n) #define sf scanf #define pf printf #define pb push_back #define MP make_pair #define fr first #define sc second #define ll long long #define dd double #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define mem(ara, value) memset(ara, value, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define SZ(a) int(a.size()) #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define take(args...) asdf,args #define dump(x) cerr<<#x<<" = "<<x<<endl #define debug(args...) cerr,args; cerr<<endl; using namespace std; template<typename T> ostream& operator<<(ostream& output, vector<T>&v) { output<<"[ "; if(SZ(v)) { output<<v[0]; } FOR(i, 1, SZ(v)) { output<<", "<<v[i]; } output<<" ]"; return output; } template<typename T1, typename T2> ostream& operator<<(ostream& output, pair<T1, T2>&p) { output<<"( "<<p.fr<<", "<<p.sc<<" )"; return output; } template<typename T> ostream& operator,(ostream& output, T x) { output<<x<<" "; return output; } struct ASDF{ ASDF& operator,(int &a) { sf("%d", &a); return *this; } ASDF& operator,(long int &a){ sf("%ld", &a); return *this; } ASDF& operator,(long long int &a){ sf("%lld", &a); return *this; } ASDF& operator,(char &c){ sf("%c", &c); return *this; } ASDF& operator,(double &d){ sf("%lf", &d); return *this; } template<typename T> ASDF& operator,(T &a){ cin>>a; return *this; } }asdf; //Header ends here #define MAXX 10007 int N, M; vector<int>adj[MAXX]; bool visited[MAXX]; int parent[MAXX]; int low[MAXX]; int disc[MAXX]; int tyme; bool isArticulationPoint[MAXX]; void init() { loop(i, MAXX) { adj[i].clear(); visited[i] = false; parent[i] = -1; isArticulationPoint[i] = false; } tyme = 0; } void dfs_articulation_point(int u) { visited[u] = true; disc[u] = low[u] = ++tyme; int cntChild = 0; loop(i, SZ(adj[u])) { int v = adj[u][i]; if( ! visited[v] ) { cntChild++; parent[v] = u; dfs_articulation_point(v); low[u] = min(low[u], low[v]); if(parent[u] != -1) { if(low[v] >= disc[u]) { isArticulationPoint[u] = true; } } } else if(v != parent[u]) { low[u] = min(low[u], disc[v]); } } if(parent[u] == -1) { if(cntChild > 1) { isArticulationPoint[u] = true; } } } int main() { int kases, kaseno = 0; take(kases); while(kases--) { take(N, M); init(); int u, v; loop(i, M) { take(u, v); adj[u].pb(v); adj[v].pb(u); } for(int i=1; i<=N; i++) { if( ! visited[i] ) { dfs_articulation_point(i); } } int cntArticulationPoint = 0; for(int i=1; i<=N; i++) { if(isArticulationPoint[i]) cntArticulationPoint++; } pf("Case %d: %d\n",++kaseno, cntArticulationPoint); } }