(LightOj) 1291 – Real Life Traffic

/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#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

vector<int>graph[MAXX];
int n, m;
map<int, map<int, int> > isBridge;




bool visited[MAXX];
int low[MAXX], disc[MAXX];
int parent[MAXX];

int t;
vector<paii>bridges;

int cnt[MAXX];

void dfs_bridge(int u)
{
	visited[u] = true;

	low[u] = disc[u] = ++t;

	loop(i, SZ(graph[u]))
	{
		int v = graph[u][i];

		if( ! visited[v])
		{
			parent[v] = u;

			dfs_bridge(v);

			low[u] = min(low[u], low[v]);

			if(low[v] > disc[u] )
			{
				bridges.pb(MP(u, v));

				isBridge[u][v] = isBridge[v][u] = 1;
			}
		}
		else if( v != parent[u])
		{
			low[u] = min(low[u], disc[v]);
		}
	}

}


int find(int u)
{
	if(u == parent[u]) return u;
	else return parent[u] = find(parent[u]);
}







int main()
{
	int kases, kaseno = 0;

	take(kases);

	while(kases--)
	{
		loop(i, MAXX) graph[i].clear();
		
		isBridge.clear();



		take(n, m);

		int u, v;

		loop(i, m)
		{
			take(u, v);

			graph[u].pb(v);
			graph[v].pb(u);
		}


		mem(visited, 0);
		mem(parent, -1);

		t = 0;
		bridges.clear();

		loop(i, n)
		{
			if(!visited[i])
			{
				dfs_bridge(i);
			}
		}

		loop(i, n)
		{
			parent[i] = i;
		}


		loop(i, n)
		{
			loop(j, SZ(graph[i]))
			{
				int v = graph[i][j];

				if(isBridge[i][v] != 1)
				{
					//cerr<<"i is "<<i<<" and v  = "<<v<<"   "<<isBridge[u][v]<<endl;
					
					int u = find(i);

					v = find(v);


					if( u != v)
					{
						parent[u] = v;

						//cerr<<"connecting "<<u<<" and "<<v<<endl;
					}
				}
				else
				{
					//dump(u); dump(v);
					//cerr<<"here"<<endl;
				}
				
			}
		}

		mem(cnt, 0);
		
		loop(i, SZ(bridges))
		{
			int u = bridges[i].fr, v = bridges[i].sc;

			u = find(u);

			v = find(v);


			//dump(u); dump(v);

			cnt[u]++;
			cnt[v]++;
		}


		int ret = 0;

		loop(i, n)
		{
			if(cnt[i] == 1)
			{
				ret++;
			}
		}


		//ret = count of leaf

		ret = (ret + 1)/2;






		pf("Case %d: %d\n", ++kaseno, ret);
	}



}