/**
 n m
 a1 b1
 ...
 am bm
*/

#include <cstdio>
#include <vector>
using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int N = 1e5;
vector<int> c[N], List[2];
int impossible, n, m, cc, u[N];

void dfs( int v, int cc ) { // O(V)
  List[cc-1].push_back(v);
  u[v] = cc;
  for (auto x : c[v]) // O(E)
    if (!u[x])
      dfs(x, 3 - cc); // 1 -> 2, 2 -> 1
    else if (u[x] == cc) 
      impossible = true;
}
int main() {
  scanf("%d%d", &n, &m);
  forn(i, m) {
    int a, b;
    scanf("%d%d", &a, &b), a--, b--; // 0..n-1
    c[a].push_back(b);
    c[b].push_back(a);
  }
  forn(i, n)
    if (!u[i])
      dfs(i, 1);
  printf("%d\n", cc);
  forn(i, n)
    printf("%d ", u[i]);
}