The Net

#include<bits/stdc++.h>

using namespace std;

int routers,par[302],cost[302],source,dest;

bool color[302],yes;

vector<int>graph[302];

void bfs()
{
    queue<int>Q;

    Q.push(source);

    color[source] = true;

    cost[source] = 0;

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

        Q.pop();

        int sz = graph[u].size();

        for(int i = 0;i<sz;i++)
        {
            int j = graph[u][i];

            if(color[j]==false)
            {
                color[j] = true;

                cost[j] = cost[u]+1;

                par[j] = u ;

                Q.push(j);

                if(j==dest)
                {
                    yes = true;

                    while(!Q.empty())
                        Q.pop();

                    break;
                }
            }
        }

        if(yes)
            break;
    }
}

void path(int u)
{
    if(u==source)
    {
        printf("%d",source);

        return;
    }
    else
    {
        path(par[u]);

        printf(" %d",u);
    }

    return;
}

int main()
{
    string s;

    int i,j,len,from,to;

    while(cin>>routers)
    {
        for(i=1; i<=routers; i++)
        {
            cin>>s;

            len = s.length();

            from = to = 0;

            int idx = 0;

            while(s[idx]!='-')
            {
                from = (from*10)+(s[idx]-48);

                idx++;
            }

            for(j=idx+1; j<len; j++)
            {
                if(s[j]>='0' && s[j]<='9')
                {
                    to = (to*10)+(s[j]-48);
                }

                if(s[j]==',' || j==len-1)
                {
                    graph[from].push_back(to);

                    to = 0;
                }
            }
        }

        int query;

        cout<<"-----\n";

        cin>>query;

        for(i=1;i<=query;i++)
        {
            cin>>source>>dest;

            yes = false;

            bfs();

            if(!yes)
            {
                cout<<"connection impossible\n";
            }
            else
            {
                path(dest);

                cout<<"\n";
            }

            memset(color,false,sizeof(color));

            memset(cost,0,sizeof(cost));

            memset(par,0,sizeof(par));
        }

        for(i=0;i<=routers;i++)
        {
            graph[i].clear();
        }
    }

    return 0;
}