UVa 10009 - All Roads Lead Where?

/*

    Accepted

    Algorithm: BFS with printing the path

*/

#include<bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define psb push_back
#define fast ios_base::sync_with_stdio(false)

typedef map<string, int>mpsi;
typedef map<int, string>mpis;

const int high = 1e5+10;

int visited[high] , par[high];
vector<int>adj[high];

mpsi mp1;
mpis mp2;

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

    mp1.clear();
    mp2.clear();
}

void CLRv2()
{
    for(int i=0; i<high; i++)
    {
        visited[i] = 0;
        par[i] = 0;
    }
}

void BFS(int s, int d)
{
    visited[s] = 1;
    queue<int>Q;

    Q.push(s);

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

        if(u == d) return;

        int sze = adj[u].size();

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

            if(!visited[v])
            {
                par[v] = u;
                visited[v] = 1;
                Q.push(v);
            }
        }
    }
}

void path(int i, int j)
{
    if(i == j)
    {
        string s = mp2[i];
    }

    else if(par[j] == 0)
    {
        cout << "No Path ";
    }

    else
    {
        path(i, par[j]);

        string s = mp2[par[j]];

        cout << s[0];
    }
}

int main()
{
    fast;
    int m , n , i , test, tc=0;
    string x , y, start, endd;

    cin >> test;

    while(test--)
    {
        CLRv1();

        if(tc) cout << "\n";
        tc = 1;

        int num = 0;

        cin >> m >> n;

        for(i=0; i<m; i++)
        {
            cin >> x >> y;

            if(mp1[x] == 0)
            {
                num += 1;

                mp1[x] = num;

                mp2[num] = x;
            }

            if(mp1[y] == 0)
            {
                num += 1;

                mp1[y] = num;

                mp2[num] = y;
            }

            adj[mp1[x]].psb(mp1[y]);
            adj[mp1[y]].psb(mp1[x]);
        }

        while(n--)
        {
            cin >> start >> endd;

            CLRv2();

            BFS(mp1[start], mp1[endd]);

            path(mp1[start], mp1[endd]);

            cout << endd[0] << "\n";
        }
    }

    return 0;
}