762_WeShipCheap

#include <bits/stdc++.h>

using namespace std;

int trace[1002];
vector <int> adj[1002];

void BFS(int s, int t) {
    queue <int> q;
    q.push(s);
    trace[s] = -1;

    while (!q.empty())
    {
        int u = q.front(); q.pop();
        if (u == t) break;

        for (int i=0; i<adj[u].size(); ++i)
        {
            int v = adj[u][i]; //cout << v << endl;
            if (!trace[v])
            {
                q.push(v);
                trace[v] = u;
            }
        }
    }
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("uva762.inp", "r", stdin);
    #endif // ONLINE_JUDGE

    bool blank = true;
    int E;
    while (scanf("%d", &E) != EOF)
    {
        if (!blank) printf("\n"); else blank = false;

        int n = 0; //m.clear(); rm.clear();
        string u, v;
        map <string, int> m;
        map <int, string> rm;

        for (int i=0; i<E; ++i)
        {
            cin >> u >> v;
            //cout << u << " " << v << " " << m[u] << " " << m[v] << endl;
            if (!m[u])
            {
                m[u] = ++n;
                rm[n] = u;
                adj[m[u]].clear();
            }
            if (!m[v])
            {
                m[v] = ++n;
                rm[n] = v;
                adj[m[v]].clear();
            }

            adj[m[u]].push_back(m[v]);
            adj[m[v]].push_back(m[u]);
        }

        cin >> u >> v;
        if (!m[u] || !m[v]) printf("No route\n");
        else
        {
            for(int i=1; i<=n; ++i) trace[i] = 0;
            BFS(m[u], m[v]);

            int s = m[u], f = m[v];
            if (!trace[f]) printf("No route\n");
            else
            {
                vector <string> ans;
                while (s != f)
                {
                    ans.push_back(rm[f]);
                    f = trace[f];
                }

                ans.push_back(rm[s]);
                for (int i=ans.size()-1; i>0; i--) cout << ans[i] << " " << ans[i-1] << endl;
            }
        }
    }

    return 0;
}