#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("fotbal2.in");
ofstream g("fotbal2.out");
 vector <int> v[50005],mt[50005];
 int n,m,a[250005],k,gr[50005],kres,win[250005];

 void Del(int x,int y)
 { int i;
    for(i=0;i<v[x].size();i++)
    if (v[x][i]==y)
      {v[x][i]=v[x][v[x].size()-1];
       mt[x][i]=mt[x][mt[x].size()-1];
      mt[x].pop_back();
       v[x].pop_back();
       break;
       }
 }

 void Euler(int x)
 { int nod;
   while(v[x].size())
   {
     nod=v[x][0];
     if (nod!=n+1 && mt[x][0]!=n+1) win[mt[x][0]]=nod;
     k++; a[k]=nod;
     Del(x,nod);
     Del(nod,x);
     x=nod;
   }
 }

 void Build()
 { int i,sol=0;
    k=1; a[k]=1;
     while(k)
     { sol++;
       Euler(a[k]); k--;

     }
  cout<<sol;
 }

int main()
{ int i,x,y,j,ok=1;
   f>>n>>m;

   for(i=1;i<=m;i++)
   { f>>x>>y;
      v[x].push_back(y);
      v[y].push_back(x);
      mt[x].push_back(i);
      mt[y].push_back(i);

     gr[x]++; gr[y]++;
   }

   for(i=1;i<=n;i++)
    if (gr[i]%2==1 || gr[i]==0)
     {v[i].push_back(n+1);
      mt[i].push_back(0);
      v[n+1].push_back(i);
      mt[n+1].push_back(0);
       if (gr[i]>0) ok=0;
     }

   Build();

   if (ok) g<<"0\n"; else g<<"2\n";


   for(i=1;i<=m;i++)
    g<<win[i]<<"\n";
    return 0;
}