Lightoj 1174 - Commandos

/*
Lionel Messi is such a player that you may catch him, you may touch him, you may feel him
and definitely you may Love him.
Lionel Messi is Messi. A little Magician in this World.

*/

/*
Run BFS from the Source and Destination besides store the distance for all nodes on two different array when you run BFS from Source and Destination.
Pick the biggest time with Summation from your stored distances... :)
You have to find the minimum time that's why you have to Visit from both Source and Destination and at last you have to pick the biggest time for the minimum ...

*/
// Algorithm: BFS
// Accepted

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 203;


struct printf
{
    void ek(int n){cout << n << "\n";}
    void dui(int x , int y) { cout << x << " " << y << "\n"; }
    void tin(int x , int y , int z) { cout << x << " " << y << " " << z << "\n"; }
}tp;

struct sieve
{
    int prm[high], plen=0;
    bitset<high>bs;
    void get_prime()
    {
        LL i , j;
        bs.set();
        bs[0]=bs[1]=0;
        for(i=2; i<=high; i++)
        {
            if(bs[i])
            {
                prm[plen++] = i;

                for(j=i*i; j<=high; j+=i) bs[j] = 0;
            }
        }
    }
    void pprm(){ for(int i=0; i<100; i++) cout << prm[i] << "; "; }
}prime;

vii adj[high];
int fromSource[high], fromDest[high];
bool visited[high] , f=false;

void BFS(int s)
{
    int v=0 , u=0;

    queue<int>Q;

    Q.push(s);

    visited[s] = true;

    while(!Q.empty())
    {
        u = Q.front();

        Q.pop();

        for(int i=0; i<adj[u].size(); i++)
        {
            v = adj[u][i];

            if(!visited[v])
            {
                Q.push(v);
                visited[v] = true;

                if(!f)
                {
                    fromSource[v] = fromSource[u] + 1;
                }

                else
                {
                    fromDest[v] = fromDest[u] + 1;
                }
            }
        }
    }
}

void CLR()
{
    for(int i=0; i<high; i++)
    {
        adj[i].clear();
    }
}

int main()
{
    //fast;
    int test, tc=0 , n , R , i , u , v , s , d , maxi = 0;
    sf("%d", &test);
    while(test--)
    {
        mset(visited , false);
        mset(fromSource , 0);
        mset(fromDest , 0);
        CLR();
        f=false;

        sf("%d %d", &n , &R);

        for(i=0; i<R; i++)
        {
            sf("%d %d", &u , &v);

            adj[u].psb(v);
            adj[v].psb(u);
        }

        sf("%d %d", &s , &d);

        BFS(s);

        f=true;
        mset(visited , false);

        BFS(d);

//        for(i=0; i<n; i++)
//        {
//            cout << i << "-" << "from Source: " << fromSource[i] << "; from Destination: " << fromDest[i] << "\n";
//        }

        maxi = 0;

        for(i=0; i<n; i++)
        {
            maxi = max(fromSource[i] + fromDest[i] , maxi);
        }

        pf("Case %d: %d\n", ++tc , maxi);
    }

    return 0;
}