#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10;
const int A = 2e4;
const int inf = 2e5;
int n, m, S, T, tot, head, tail, p[maxn], q[maxn], d[maxn], h[maxn];
struct Edge { int to, w, nxt; } e[maxn];
vector<pair<int, int> > g;
void addedge(int u, int v, int w) { e[tot] = { v, w, h[u] }; h[u] = tot++; e[tot] = { u, 0, h[v] }; h[v] = tot++; }
bool bfs() {
    memset(d, 0, sizeof(d));
    head = tail = 0; q[tail++] = S; d[S] = 1;
    while (head < tail) {
        int u = q[head++];
        for (int k = h[u]; ~k; k = e[k].nxt) {
            int v = e[k].to, w = e[k].w;
            if (!w || d[v]) continue;
            q[tail++] = v; d[v] = d[u] + 1;
            if (v == T) return true;
        }
    } return false;
}
int dfs(int u, int cur) {
    if (u == T) return cur; int val = 0;
    for (int& k = p[u]; ~k; k = e[k].nxt) {
        int v = e[k].to, w = e[k].w;
        if (d[u] + 1 != d[v] || !w) continue;
        int W = dfs(v, min(cur - val, w));
        if (!W) d[v] = -1;
        e[k].w -= W; e[k ^ 1].w += W; val += W;
        if (val == cur) break;
    }  return val;
}
bool check(int x) {
    memset(h, -1, sizeof(h)); tot = 0;
    S = n + A + 1; T = S + 1;
    for (int i = 1; i <= m; i++) {
        auto [u, v] = g[i - 1]; addedge(S, i, 1);
        addedge(i, u + A, 1); addedge(i, v + A, 1);
    }
    for (int i = 1; i <= n; i++)
        addedge(i + A, T, x);
    int res = 0; while (bfs()) {
        for (int i = 1; i <= T; i++) p[i] = h[i];
        res += dfs(S, inf);
    } return res >= m;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m; g.resize(m);
    for (auto& [u, v] : g) cin >> u >> v;
    int l = m / n, r = m, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    } cout << ans << '\n';
    for (int i = 0; i < m; i++)
        cout << (e[i * 6 + 2].w == 0) << '\n';
    return 0;
}