Graph Marathon - May 2021 - Problem ::: F

/*
            BISMILLAHIR-RAHMANIR-RAHIM
                    SWExSh4n.t0
                        SUST
*/
#include <bits/stdc++.h>
using namespace std;

std::priority_queue < std::pair < int , int > > pq;
std::vector < std::vector < int > > G;
std::vector < std::vector < int > > H;
std::vector < bool > vis;
std::vector < bool > vis2;
std::vector < int > koyjon_ke_dey;
std::set < int > set1;  //   true-in true-out
std::set < int > set2;  //  false-in true-out

int bfs ( int src, int n )
{
    vis2.clear();
    vis2.resize(n);
    std::queue < int > q;
    q.push(src);
    vis2[src] = true;

    int u, cnt = 1;

    while( !q.empty() )
    {
        u = q.front(); q.pop();
        for( auto v : G[u] )
        {
            if( !vis2[v] )
            {
                vis2[v] = true;
                q.push(v);
                cnt++;
            }
        }
    }

    return cnt;
}

void khela_hobe( int src, int n )
{
    std::queue < int > q;
    q.push(src);
    vis[src] = true;
    koyjon_ke_dey[src] = 0;
    set1.clear();
    set2.clear();

    int u, v, mx , mn, mxIndx, mnIndx;

    mx = mn = koyjon_ke_dey[src];
    mxIndx = mnIndx = src;

    //  just find out the sub-graph
    while( !q.empty() )
    {
        u = q.front(); q.pop();
        if( H[u].size() ) {
            set1.insert(u);
        }
        else {
            set2.insert(u);
        }
        for( int i = 0; i < G[u].size(); i++ ) {
            v = G[u][i];
            if( !vis[v] )
            {
                vis[v] = true;
                q.push(v);
            }
        }
        for( int i = 0; i < H[u].size(); i++ )
        {
            v = H[u][i];
            if( !vis[v] )
            {
                vis[v] = true;
                q.push(v);
            }
        }
    }

    // find out the best leader in the sub-graph
    std::pair < int , int > p_air;
    if( set2.size() == 0 )
    {
        p_air.first = set1.size();
        p_air.second = n;
        for( auto x : set1 )
        {
            if( x < p_air.second ) p_air.second = x;
        }
        p_air.second *= -1;
        pq.push(p_air);
    }
    else {
        for( auto srcc : set2 )
        {
            p_air.first = bfs( srcc, n );
            p_air.second = -srcc;
            pq.push(p_air);
        }
    }
}

void init ( int n )
{
    G.clear();
    G.resize(n);
    H.clear();
    H.resize(n);
    vis.clear();
    vis.resize(n);
    koyjon_ke_dey.clear();
    koyjon_ke_dey.resize(n);

    while ( !pq.empty() )
        pq.pop();
}

int main()
{
    int t, cs = 0;
    std::cin >> t;
    int n, u, v;

    while( t-- ) {
        std::cin >> n;
        init(n);
        for( int i = 0; i < n; i++ ) {
            std::cin >> u >> v;
            u--, v--;
            G[u].push_back(v);
            H[v].push_back(u);
        }

        for( int i = n-1; i >= 0; i-- ) {
            if( !vis[i] ) {
                khela_hobe( i, n );
            }
        }

        std::cout << "Case " << ++cs << ": " << -pq.top().second + 1 << endl;
    }
    return 0;
}

//  ALHAMDULILLAH