#include <cassert>
#include <fstream>
#include <string.h>
#include <list>


using namespace std;

int n, m, a, b; // n numero di nodi, m numero di archi(e di righe+1), a nodo di partenza, b nodo di arrivo
int archiRimanenti;


list<int> *vicini;

void calcolaPercorso(int a);
bool percorsoValido(int a,int v);
int contaNodiRaggiungibili(int a, bool visitati[]);
void rimuoviArco(int u, int v);
bool controllaNodoN(int v);

int main(){


    ifstream fin("input.txt"); assert( fin );
    fin >> n >> m >> a >> b;                   //Leggo la prima riga

    archiRimanenti = m;
    vicini = new list<int>[n+1];                 // Creo la lista di adiacenza dei nodi

    int u,v; // Interi temporanei per l'inserimento nella lista

    for (int i = 0; i < m; i++) { //Inserisco i dati nella lista
      fin >> u >> v;
      vicini[u].push_back(v);
      vicini[v].push_back(u);
    }
    fin.close();

    ofstream fout1;
    fout1.open ("output.txt",ios::out);
    fout1.close();

    calcolaPercorso(a);

    ofstream fout;
    fout.open ("output.txt",ios::app);
    fout << "\n" << endl;
    fout.close();

}


//Funzione ricorsiva che calcola il percorso. Utilizza della funzioni Ausiliarie.
void calcolaPercorso(int a){

     list<int>::iterator i;
     for(i = vicini[a].begin(); i != vicini[a].end(); ++i){
         int v = *i;
         if(v!= -1 && percorsoValido(a,v)){
             if(((v == n) && controllaNodoN(v)) || v != n){
                ofstream fout;
                fout.open ("output.txt",ios::app);
                fout << a << " " << v << endl;
                fout.close();
                rimuoviArco(a,v);
                archiRimanenti--;
                calcolaPercorso(v);
             }else if((v == n) && !controllaNodoN(v) && archiRimanenti == 1){
                 ofstream fout;
                 fout.open ("output.txt",ios::app);
                 fout << a << " " << v << endl;
                 fout.close();
                 rimuoviArco(a,v);
             }else { }
         }
      }
}

//Funzione che controlla se l'arco che calcolaPercorso sta scegliendo è un arco valido.
bool percorsoValido(int a,int v){

    /*Ci sono 2 casi:
     *L'arco è l'unico che esce dal vertice a. Allora si sceglie quello.
     *Ci sono più archi adiacenti. Allora bisogna effettuare dei controlli.
     */

    //L'arco è l'unico che esce dal nodo
    list<int>::iterator i;
    int count = 0;
    for(i = vicini[a].begin(); i != vicini[a].end(); ++i){
        if(*i != -1)
            count ++;
    }
    if(count == 1)
        return true;

    //Ci sono più archi che escono dal nodo

    bool visitati[n];
    memset(visitati,false,n);

    int count1 = contaNodiRaggiungibili(a,visitati);

    rimuoviArco(a,v);
    memset(visitati,false,n);
    int count2 = contaNodiRaggiungibili(a,visitati);
    vicini[a].push_back(v);
    vicini[v].push_back(a);

    if(count1 > count2)
        return false;
    else return true;

}

// Devo verificare che un arco verso il nodo n sia una scelta accettabile un quel momento
bool controllaNodoN(int v){

    list<int>::iterator i;
    int count = 0;
    for(i = vicini[v].begin(); i != vicini[v].end(); ++i){
        if(*i != -1)
            count ++;
    }
    if(count > 1)
       return true;
    else return false;
}


int contaNodiRaggiungibili(int a, bool visitati[]){
    visitati[a] = true;
    int count = 1;

    list<int>::iterator i;
    for(i = vicini[a].begin(); i != vicini[a].end(); ++i){
        if(*i != -1 && !visitati[*i])
            count += contaNodiRaggiungibili(*i,visitati);
    }
    return count;
}


void rimuoviArco(int u, int v){

    list<int>::iterator i;
    for(i = vicini[u].begin(); i != vicini[u].end(); ++i){
        if(*i == v)
            *i = -1;
    }

    list<int>::iterator j;
    for(j = vicini[v].begin(); j != vicini[v].end(); ++j){
        if(*j == u)
            *j = -1;
    }

}