Back to Underworld

The Vampires and Lykans are fighting each other to death. The war has become so fierce that, none knows who will win. The humans want to know who will survive finally. But humans are afraid of going to the battlefield.

So, they made a plan. They collected the information from the newspapers of Vampires and Lykans. They found the information about all the dual fights. Dual fight means a fight between a Lykan and a Vampire. They know the name of the dual fighters, but don't know which one of them is a Vampire or a Lykan.

So, the humans listed all the rivals. They want to find the maximum possible number of Vampires or Lykans.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 10⁵), denoting the number of dual fights. Each of the next n lines will contain two different integers u v (1 ≤ u, v ≤ 20000) denoting there was a fight between uand v. No rival will be reported more than once.

Output

For each case, print the case number and the maximum possible members of any race.

Sample Input	Output for Sample Input
2 2 1 2 2 3 3 1 2 2 3 4 2	Case 1: 2 Case 2: 3

Note

Dataset is huge, use faster I/O methods.

###############################editorial ##########################################

in this problem we need to find  maximum no  of node which can be coloured with same colour .

so we treat each disconnected components as different problem and .. for each dissconnected component we  colour this disconected  component  whith two different colours (colur which is not used yet in any other disconnected component ) ... and finally we find sum of (maxim from each disconnected components ).. since that maximium  sinc all those  nodes can be coloured with same colour .......(think ..)

################################code ###################

#include<iostream>

using namespace std;

#include<bits/stdc++.h>

 int read_int(){

char r;

bool start=false,neg=false;

int ret=0;

while(true){

r=getchar();

if((r-'0'<0 || r-'0'>9) && r!='-' && !start){

continue;

}

if((r-'0'<0 || r-'0'>9) && r!='-' && start){

break;

}

if(start)ret*=10;

start=true;

if(r=='-')neg=true;

else ret+=r-'0';

}

if(!neg)

return ret;

else

return -ret;

}

int bfs(int pos,int val,int visited[],list<int>li[])

 {

    queue<int >q;

    q.push(pos);

      while(!q.empty())

       {

          int start=q.front();

          q.pop();

          list<int> :: iterator it;

          for(it=li[start].begin();it!=li[start].end();it++)

           {

            if(visited[*it]==0)

            {

            visited[*it]=-1*visited[start];

            q.push(*it);

            }

           }

       }

 }

int main()

{

int tt;

cin>>tt;

int t=1;

   while(tt--)

    {

    int n;

   

    n=read_int();

      int visited[20000+10];

      list<int> li[20000+10];

      

      for(int i=1;i<=n;i++)

       {

           int a,b;

          // cin>>a>>b;

           a=read_int();

           b=read_int();

           li[a].push_back(b);

           li[b].push_back(a);

           

           

       }

      for(int i=0;i<=20010;i++) visited[i]=0;

       

       int ll=1;

        

        for(int i=1;i<=20000;i++)// call bfs for all disconnected components 

         {

          if(!visited[i] && !li[i].empty())

           {

           visited[i]=ll;

            bfs(i,-ll,visited,li);// fill with ll colour

            ll++;

           }

         }

       

       

         int ans=0;

         for(int i=1;i<ll;i++)// find no of node coloured with i and  -i colour and ans=max (a1,a2)

          {

          int a1=0,a2=0;

          for(int j=0;j<=20000+1;j++)

          {

          if(visited[j]==i) a1++;

          if(visited[j]==-1*i) a2++;

          }

          ans+=max(a1,a2);

           

          }

       

    cout<<"Case "<<t++<<":"<<" "<<ans<<endl;

     

    }

    return 0;

}