UVa 762 :: ACCEPTED

//RE is not mightier than me

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

vector<int> G[mx];
int cr=0;


void clean(int cr) {
    for(int i=0; i<=cr; i++)
        G[i].clear();
    return;
}

int bfs(string src, string dst, map<string,int> mp, string *id, bool *visited, int *parent) {

    int nodeLevel[cr];
    memset(nodeLevel, 0, sizeof nodeLevel);

    if(src==dst){
        cout<<src<<" "<<dst<<endl;
        return 0;
    }

    //cout<<"Source and destination is not equal"<<endl;

    queue<int> sack;
    sack.push(mp[src]);
    visited[mp[src]]= true;
    nodeLevel[mp[src]]=0;

    while(!sack.empty()) {
        int top= sack.front();
//        cout<<"Top found is: "<<id[top]<<endl;
        sack.pop();

        for(int i=0; i<G[top].size(); i++) {

            if(!visited[G[top][i]]) {
//                cout<<"Dealing with: "<<id[G[top][i]]<<endl;
                nodeLevel[G[top][i]]= nodeLevel[top] + 1;
//                cout<<"Node Level of "<<id[G[top][i]]<<" is: "<<nodeLevel[G[top][i]]<<endl;
                visited[G[top][i]]= true;
                sack.push(G[top][i]);
                parent[G[top][i]]= top;

                if(G[top][i]==mp[dst]) {
//                    cout<<"Node Level of destination is: "<<nodeLevel[G[top][i]]<<"("<< id[G[top][i]] <<")"<<endl;
                    return nodeLevel[G[top][i]];
                }
            }
        }
    }
    return -1;
}

int main() {

    //freopen("input.txt", "r", stdin);

    int n;
    bool flag= false;
    while(cin>>n) {
        cr=0;
        string id[(2*n)+3];
        int parent[(2*n)+3];
        memset(parent, 0, sizeof parent);
        bool visited[(2*n)+3];
        memset(visited, false, sizeof visited);

        string x, y;
        map<string,int> mp;
        map<int,string> mpp;

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

            if(mp[x]==0 || mp[x]== NULL) {
                ++cr;
                mp[x]= cr;
                mpp[cr]= x;
                id[mp[x]]= x;
            }
            if(mp[y]==0 || mp[y]==NULL) {
                ++cr;
                mp[y]= cr;
                mpp[cr]= y;
                id[mp[y]]= y;

            }

            G[mp[x]].push_back(mp[y]);
            G[mp[y]].push_back(mp[x]);
        }

        string src, dst;
        cin>>src>>dst;

//        cout<<"Entering bfs"<<endl;
        int reko= bfs(src, dst, mp, id, visited, parent);
//        cout<<"Didn't make to the bfs"<<endl;
//    cout<<"VALUE OF REKO IS: "<<reko<<endl;

        if(flag) cout<<endl;
        flag= true;

        if(reko>0) {
            string newSrc= dst;
            string node;
            string path[reko+2];
            int cnt=0;
            int pre=reko;
            int indexer=reko;
            while(reko--) {
                path[indexer]= newSrc;

                node.clear();
                node= id[parent[mp[newSrc]]];
                newSrc.clear();
                newSrc= node;
                ++cnt;
                --indexer;
            }

            path[0]= src;

            for(int i=0; i<cnt; i++) {
                cout<<path[i]<<" "<<path[i+1]<<endl;
            }

        } else if(reko==-1) cout<<"No route"<<endl;
        clean(cr);
    }
    return 0;
}