#include <cassert>
#include <iostream>  
#include <fstream>
#include <string>

using namespace std;
const int MAX_N = 45000;
const int MAX_M = 45000;
bool matrice[MAX_N][MAX_M];
int n, m, a, b; 


int main()
 {
  ifstream fin("input.txt"); assert( fin );
  fin >> n >> m >> a >> b;
  int i,j, temp1, temp2;
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
     matrice[i][j] = 0;
  i=a-1;
  j=m;
  
  
  while(j>0)
  {
    fin >> temp1 >> temp2;
    matrice[temp1-1][temp2-1]=1;
    matrice[temp2-1][temp1-1]=1;
    cout << j <<endl;
    j--;
  }
  fin.close();
  ofstream fout("output.txt"); assert( fout );
  while(m>1)
  {
    for(j=0;j<n;j++)
    {
      
      if(matrice[i][j]==1)
      {
          
            matrice[i][j]=0;
            matrice[j][i]=0;
            m--;
            fout << i+1 << " " << j+1 << endl;
            i=j;
            j=-1;
         
      }
       
    }    
  }

  if(matrice[i][j]==1 && j==b-1 && m==1)
  {
          
          fout << i+1 << " " << j+1 << endl;
          m=0;
          j=n;
  }      
  
  
  
  fout.close();
  return 0;
}