#include <iostream>
#include <vector>

using namespace std;



struct pionki
{
    int pionek;
    pionki * next;
    pionki()
    {
        next = 0;
    }
};

struct kolejka
{
    pionki * pierwszy;
    pionki* ostatni;
    //int f = 1;
    kolejka()
    {
        pierwszy = 0;
    }

    void dodaj(int pionek)
    {
        if(pierwszy == 0){
            ostatni = new pionki;
            ostatni->pionek = pionek;
            pierwszy = new pionki;
            pierwszy->pionek = pionek;
            pierwszy->next = ostatni;
        }
        else{
            pionki * nowy = new pionki;
            nowy->pionek = pionek;
            ostatni->next = nowy;
            ostatni = nowy;
        }

    }

    int * zdejmij(int n)
    { int *tab = new int[n];
        pionki * pom = pierwszy;
        pom = pom->next;
        for(int i = 0; i<n;i++){
            tab[i] = pom->pionek;
            pom = pom->next;
        }
        return tab;
    }

    void show()
    {
        if(pierwszy != 0){
        pionki * pom = pierwszy;
        pom = pom->next;
        while(pom){
            cout<<pom->pionek<<" ";
            pom = pom->next;
        }
        }
    }



    bool exist(int w)
    {
        pionki * pom = pierwszy;
        pom = pom->next;
        while(pom){
            //cout<<pom->pionek<<" ";
            if(w == pom->pionek)
                return true;
            pom = pom->next;

        }
        return false;
    }
    short last()
    {
        pionki * pom = pierwszy;
        if(pom){
            if(pom->next){
                while(pom->next->next){
                    pom = pom->next;
                }
                return pom->pionek;
            }
        }
    }
    int ost()
    {
        return ostatni->pionek;
    }
};





struct Wierzcholek;

struct Krawedz
{
    Wierzcholek* koniec;
    int waga;

    Krawedz(int waga, Wierzcholek *start)
    {
        this->waga=waga;
        koniec=start;
    }
};

struct Wierzcholek
{
    int klucz;
    Wierzcholek *poprzednik;
    int odleglosc;
    vector<Krawedz*> sasiedzi;

    Wierzcholek(int klucz)
    {
        this->klucz=klucz;
    }

    Wierzcholek();
};

class Graf
{
public:
    vector<Wierzcholek*> wierzcholki;

    void dodajWierzcholek(int a)
    {
        Wierzcholek *w = new Wierzcholek(a);
        wierzcholki.push_back(w);
    }

    void dodajKrawedz(int a, int b, int waga)
    {
        if(a != b){
            int dl=wierzcholki.size();
            Wierzcholek *w1;
            Wierzcholek *w2;
            for(int i=0; i<dl; i++)
            {
                if(wierzcholki[i]->klucz == a)
                    w1 = wierzcholki[i];
                else if(wierzcholki[i]->klucz == b)
                    w2 = wierzcholki[i];
            }
            Krawedz *krawedz = new Krawedz(waga,w2);
            w1->sasiedzi.push_back(krawedz);
            Krawedz *k2 = new Krawedz(waga,w1);
            //krawedz = new Krawedz(waga,w1);
            w2->sasiedzi.push_back(k2);
        }
    }

    Wierzcholek * findPoKluczu(int a)
    {
        for(int i = 0; i< wierzcholki.size();i++){
            if(wierzcholki[i]->klucz == a){
                return wierzcholki[i];
            }
        }
        Wierzcholek * w = new Wierzcholek(2147483645);
        return w;
    }



// s - wierzcholek startowy, wyznaczenie najkrótszej drogi do ka¿dego z pozosta³ych wierzcho³ków
    void algorytmDijkstry(Wierzcholek *s)
    {
        inicjalizuj(s);
        vector<Wierzcholek*> Q = this->wierzcholki;
        int dl=Q.size();
        Wierzcholek *u;
        int j;
        while(!Q.empty())
        {
            u=Q[0];
            j=0;
            dl=Q.size();
            for(int i=1; i<dl; i++)
            {
                if(Q[i]->odleglosc < u->odleglosc)
                {
                    u=Q[i];
                    j=i;
                }
            }
            Q.erase(Q.begin()+j);

            for(int i=0; i<u->sasiedzi.size(); i++)
            {
                if(u->sasiedzi[i]->koniec->odleglosc > (u->odleglosc + u->sasiedzi[i]->waga))
                {
                    u->sasiedzi[i]->koniec->poprzednik=u;
                    u->sasiedzi[i]->koniec->odleglosc=u->odleglosc + u->sasiedzi[i]->waga;
                }
            }
        }
    }

    void inicjalizuj(Wierzcholek* s)
    {
        for(int i=0; i<this->wierzcholki.size(); i++)
        {
            this->wierzcholki[i]->odleglosc=2147483645;
        }
        s->odleglosc=0;
    }

    void drukuj()
    {
        for(int i=0; i<wierzcholki.size(); i++){
        cout<<"Sasiedzi wierzcholka "<<wierzcholki[i]->klucz<<": ";
        for(int j = 0; j<wierzcholki[i]->sasiedzi.size();j++)
            cout<<wierzcholki[i]->sasiedzi[j]->koniec->klucz<<" ";
        cout<<endl;
    }
    }






};

bool exist(vector <int> w,int pom)
{ int i = 0,n;
    cout<<"Elementy wektora: ";
    while(!w.empty()){
        cout<<w[i];
        if(w[i] == pom)
            return true;
        i++;
    }
    return false;
}

int main()
{
    int wierzcholki,krawedzie, pom1, pom2,p,o;
    bool ruch_p1 = false, ruch_p2 = false, byl_ruch = false;
    Graf *graf = new Graf();
    Wierzcholek * cel;

    kolejka wystapienia;
    kolejka odwiedz;

    cin>>wierzcholki;
    cin>>krawedzie;

    cin>>pom1;
    wystapienia.dodaj(pom1);
    cin>>pom2;
    wystapienia.dodaj(pom2);
    graf->dodajWierzcholek(pom1);
    graf->dodajWierzcholek(pom2);
    graf->dodajKrawedz(pom1,pom2,1);
    //cout<<"przeszlo"<<endl;
    for(int i = 1; i < krawedzie;i++){
        cin>>pom1;
        //cout<<"pobrano pierwszy"<<endl;
        if(wystapienia.exist(pom1) == false){
            wystapienia.dodaj(pom1);
            graf->dodajWierzcholek(pom1);
           // cout<<"Dodano w " <<i<<" obrocie pierwszy wierzcholek"<<endl;
        }
        cin>>pom2;
        //cout<<":))"<<endl;
        if(wystapienia.exist(pom2) == false){
            wystapienia.dodaj(pom2);
            graf->dodajWierzcholek(pom2);
            //cout<<"Dodano w " <<i<<" obrocie drugi wierzcholek"<<endl;
        }
        graf->dodajKrawedz(pom1,pom2,1);
    /*
        graf->dodajWierzcholek(pom1);
        graf->dodajWierzcholek(pom2);
        graf->dodajKrawedz(pom1,pom2,1);  */
    }
    cin>>p;
    Wierzcholek * p1 = new Wierzcholek(p);
    cin>>p;
    Wierzcholek * p2 = new Wierzcholek(p);
    Wierzcholek * temp1;
    Wierzcholek * temp2;
    cin>>o;
    for(int i = 0; i<o;i++){
        cin>>pom1;
        odwiedz.dodaj(pom1);
    }
    //cout<<"ODWIEDZINY: ";
    //odwiedz.show();
    //cout<<endl;


    //graf->drukuj();
    //cout<<endl;
    //cout<<"Elementy do odwiedzenia: "<<endl;
    //odwiedz.show();

//    int check = odwiedz.zdejmij();
    //cout<<"CHECK: "<<check<<endl;
  //  check = odwiedz.zdejmij();
    //cout<<"CHECK: "<<check<<endl;


    int * tab = odwiedz.zdejmij(o);
    kolejka wyjscie;
    //wyjscie.show();



    //cout<<"Wynik:)) : ";

    for(int i = 0; i<o;i++){
        //cout<<"tab[i]: "<<tab[i]<<endl;


        cel = graf->findPoKluczu(tab[i]);
        if(cel->klucz == 2147483645){
            cout<<"Brak połączenia z wierzchołkiem "<<tab[i]<<endl;
            return 0;
        }
        //cout<<"Zadany wierzcholek: "<<cel->klucz<<endl;
        graf->algorytmDijkstry(cel);
        p1 = graf->findPoKluczu(p1->klucz);
        p2 = graf->findPoKluczu(p2->klucz);

        if(graf->findPoKluczu(p1->klucz)->odleglosc == 2147483645 && graf->findPoKluczu(p2->klucz)->odleglosc == 2147483645){
            cout<<"Brak połączenia z wierzchołkiem "<<tab[i]<<endl;
            return 0;
        }


        if(p1->odleglosc < p2->odleglosc){
            wyjscie.dodaj(1);
            ruch_p1 = true;
            ruch_p2 = false;
            byl_ruch = true;
            p1 = cel;
        }
        if(p1->odleglosc > p2->odleglosc){
            wyjscie.dodaj(2);
            ruch_p2 = true;
            ruch_p1 = false;
            byl_ruch = true;
            p2 = cel;
        }
        if(p1->odleglosc == p2->odleglosc){
            if(byl_ruch == false){
                wyjscie.dodaj(1);
                ruch_p1 = true;
                ruch_p2 = false;
                byl_ruch = true;
                p1 = cel;
            }
            else{
                if(ruch_p2 == true){
                    wyjscie.dodaj(1);
                    ruch_p1 = true;
                    ruch_p2 = false;
                    byl_ruch = true;
                    p1 = cel;
                }
                else{
                    wyjscie.dodaj(2);
                    ruch_p2 = true;
                    ruch_p1 = false;
                    byl_ruch = true;
                    p2 = cel;
                }
            }
        }

    }
    wyjscie.show();

    /*
    cout<<"Zadany wierzcholek: "<<graf->wierzcholki[4]->klucz<<endl;
    for(int i=0; i<graf->wierzcholki.size(); i++)
    {
        cout << "Klucz: " <<graf->wierzcholki[i]->klucz <<endl<< "Odleglosc od wierzcholka startowego: "<< graf->wierzcholki[i]->odleglosc << endl<<"Klucz poprzednika: " << graf->wierzcholki[i]->poprzednik->klucz << endl;
        cout<<"######################################"<<endl;
    }
    cout<<endl<<"Graf po algorytmie: "<<endl;
    graf->drukuj();
    */

    return 0;
}