#include <fstream>
using namespace std;
ifstream in ("fotbal2.in"); ofstream out ("fotbal2.out");

int n,k;
int v[50002];
int win[50002];
int main()
{
  in >> n >> k;
  int iW=0;
  for(int i = 0; i < k; i++)
  {
    int e1,e2;
    in >> e1 >> e2;
    if(v[e1]>=v[e2])
    {
      v[e1]--;v[e2]++;
      win[iW++]=e2;
    }
    else
    {
      v[e1]++;v[e2]--;
      win[iW++]=e1;
    }
  }
  int maxP=0,minP=100000;
  for(int i = 1; i <=n; i++)
  {
    if(v[i]>maxP)maxP=v[i];
    if(v[i]<minP)minP=v[i];
  }
  out << maxP-minP << '\n';
  for(int i = 0;i < iW; i++)
  {
    out << win[i] << '\n';
  }
  return 0;
}