UVa 762 We Ship Cheap

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678
#define sz 100007

map<string,int> mp;
map<int,string> mp1;

vector<int> adj[sz];
int vis[sz];
int par[sz];

void BFS(int src)
{
    queue <int> bfsq;
    bfsq.push(src);

    vis[src] = 1;
    par[src] = src;

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

        REP(i,SZ(adj[u]))
        {
            int v = adj[u][i];

            if(vis[v]==0)
            {
                vis[v] = 1;
                par[v]=u;
                bfsq.push(v);
            }
        }
    }
    bfsq.pop();
}


void path_print(int i)
{
    if(par[i]==i) return ;
    else
    {
        path_print(par[i]);
        prii(mp1[par[i]], mp1[i]);
    }
}

void init()
{
    REP(i,sz) par[i] = i;

    mem(vis,0);

    REP(i,sz)  adj[i].clear();

    mp.clear();
    mp1.clear();
}

int main()
{
  //  freopen("F:/fout.txt", "w", stdout);
    ll n,tc=0;
    string sa,sb;

    while(scl(n)==1)
    {
        if(tc>0) puts(""); tc++;

        int mrk = 1;

        init();

        REP(i,n)
        {
            cin>>sa>>sb;

            if(mp[sa]==0) mp1[mrk] = sa , mp[sa] = mrk++;
            if(mp[sb]==0) mp1[mrk] = sb , mp[sb] = mrk++;

            adj[ mp[sa] ].pb(mp[sb]);
            adj[ mp[sb] ].pb(mp[sa]);
        }

        cin>>sa>>sb;

        if(mp[sa]==0) mp1[mrk] = sa , mp[sa] = mrk++;
        if(mp[sb]==0) mp1[mrk] = sb , mp[sb] = mrk++;

        BFS(mp[sa]);

        if(vis[mp[sb]]==0)
        {
            puts("No route");
        }
        else path_print(mp[sb]);
    }
    return 0;
}