LOJ: 1230 - Placing Lampposts

LOJ: 1230 - Placing Lampposts
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     1000002
#define inf    2000000000
#define MD     1000000000LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
pii dp[MX+2][2];
bool vis[MX+2];

pii operator + (pii A,pii B) {
    return mpp(A.X+B.X,A.Y+B.Y);
}
pii go(int p,int pp,int f) {
    vis[ p ]=1;
    pii &ret=dp[p][f];
    if(ret.X!=-1) return ret;
    ret=mpp(0,0);
    for(int i=0; i<SZ(G[p]); i++) {
        int v=G[p][i];
        if(v==pp)continue;
        if( f==1 ) {
            pii bb=pii( 0,0 )+go( v,p,0 ); ///Dont clr it
            pii aa=pii( 1,1 )+go( v,p,1 ); ///Color it
            int a=0,b=0;
            if( aa.X==bb.X ) {
                a+=aa.X;
                b+=max( aa.Y,bb.Y );
            } else if(aa.X<bb.X) {
                a+=aa.X,b+=aa.Y;
            } else {
                a+=bb.X,b+=bb.Y;
            }
            ret=(ret+mpp(a,b));
        } else {
            pii aa=pii( 1,0 )+go( v,p,1 ); ///Color it
            ret=(ret+aa);
        }
    }
    return ret;
}

int main() {
    int tc,cs=1,i,j,n,m,k,x,y;
    S(tc);
    while(tc--) {
        S2(n,m);
        fr(i,1,n)G[i].clear();
        fr(i,1,m) {
            S2(x,y);
            x++,y++;
            G[x].pb(y);
            G[y].pb(x);
        }
        fr(i,1,n)fr(j,0,1)dp[i][j]=mpp(-1,-1);
        int a=0,b=0;
        CLR(vis);
        for(int i=1; i<=n; i++) {
            if(!vis[i]) {
                pii bb=mpp(1,0)+go(i,-1,1);
                pii aa=go(i,-1,0);
                if( aa.X==bb.X ) {
                    a+=aa.X;
                    b+=max( aa.Y,bb.Y );
                } else if(aa.X<bb.X) {
                    a+=aa.X,b+=aa.Y;
                } else {
                    a+=bb.X,b+=bb.Y;
                }
            }
        }
        printf("Case %d: %d %d %d\n",cs++,a,b,m-b);
    }
    return 0;
}