#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <cstring>
#include <stack>

#define MAX 200000

using namespace std;

ifstream fin ("2sat.in");
ofstream fout ("2sat.out");

bool check[MAX + 5];
int n, m, a, b, ctc[MAX + 5];
vector<int> v[MAX + 5],rev[MAX+5];

stack<int> st;

void dfs(int x)
{
    check[x] = 1;
    for(auto i : v[x])
        if(!check[i])
            dfs(i);
    st.push(x);
}

void dfs2(int x, int ct)
{
    check[x] = 1;
    ctc[x] = ct;
    for(auto i : rev[x])
        if(!check[i])
            dfs2(i, ct);
}

int neg(int x)
{
    if(x < n)
        return x + (n - x) * 2;
    else
        return x - (x - n) * 2;
}

int main()
{
   fin >> n >> m;
   for(int i = 1;i <= m; ++i) {
       fin >> a >> b;
       a += n, b += n;
       v[neg(a)].push_back(b);
       v[neg(b)].push_back(a);
       rev[a].push_back(neg(b));
       rev[b].push_back(neg(a));
   }
   for(int i = 0;i <= n * 2; i++)
   {
       if(i == n)
         continue;
       if(!check[i])
            dfs(i);
   }
   int ct = 0;
   memset(check, false, sizeof(check));
   while(!st.empty())
   {
       int x = st.top();
       if(!check[x])
          dfs2(x, ++ct);
       st.pop();
   }
   cout << ct << '\n';
   for(int i = 0;i < n; ++i){
       if(ctc[i] == ctc[2 * n - i]) {
           fout << -1;
           return 0;
       }
   }
   for(int i = n + 1;i <= 2 * n; ++i) {
       fout << (ctc[i] > ctc[i - 2 * (i - n)]) << ' ';
   }
}