Light OJ 1063 / Articulation Point

/***
 created: 2022-04-12-14.23.55
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll a[200005];
vector<ll>g[200005];
bool v[200005];
ll timer;
ll low[200005],in[200005];


void dfs(ll vertex,ll parent)
{
    v[vertex]=1;

    low[vertex] = in[vertex] = ++timer;

    ll edge=0;

    for(auto child:g[vertex])
    {
        if(child==parent) continue;

        if(v[child])
        {
            low[vertex]=min(low[vertex],in[child]);
        }
        else
        {
            dfs(child,vertex);

            if(low[child]>=in[vertex] && parent!=-1)
            {
                a[vertex]=1;
            }
            low[vertex]=min(low[vertex],low[child]);

            edge++;
        }
    }

    if(parent==-1 && edge>1)
    {
        a[vertex]=1;
    }
}


void clr(ll n)
{
    for(ll i=0; i<n+4; i++)
    {
        g[i].clear();
        v[i]=0;
        low[i]=-1;
        in[i]=-1;
        a[i]=0;
    }

    timer=0;
}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m,i,j,k,l;

        cin>>n>>m;

        clr(n+2);

        for(i=0; i<m; i++)
        {
            cin>>j>>k;
            g[j].push_back(k);
            g[k].push_back(j);

        }

        for(i=1; i<=n; i++)
        {
            if(v[i]==0)
            {
                dfs(i,-1);
            }
        }

        l=0;

        for(i=1; i<=n; i++)
        {
            if(a[i]==1) l++;
        }

        cout<<"Case "<<cs<<": "<<l<<nl;

    }

    get_lost_idiot;

}