#include <bits/stdc++.h>
using namespace std;
#define MAXN 10069
int Deg[MAXN];
int Edge[MAXN]; //0 mniejszy -> wiekszy;
bool isBigger[MAXN];
int n,m,v,a,b;
vector <vector <pair<int,int>>> Graph(MAXN); //to-ind

int BFS (int node, vector <bool> &Vis, vector <pair<int,int>> &Fath)
{
    queue <int> Q;
    Q.push(node);

    while (Q.size())
    {
        node = Q.front();
        Q.pop();
        if (Vis[node]) continue;

        Vis[node] = true;
        for (auto nei:Graph[node])
        {
            if (Vis[nei.first] == false)
            {
                if (node > nei.first && Edge[nei.second] == 0)
                {
                    Fath[nei.first] = make_pair(node, nei.second);
                    if (Deg[v]-1 > Deg[nei.first]) return nei.first;
                    Q.push(nei.first);
                }
                else if (node < nei.first && Edge[nei.second] == 1)
                {
                    Fath[nei.first] = make_pair(node, nei.second);
                    if (Deg[v]-1 > Deg[nei.first]) return nei.first;
                    Q.push(nei.first);
                }
            }
        }
    }

    return v;
}

inline void scan (int &number)
{
    number = 0;
    for (register int c=getchar(); (c>47 && c<58); c=getchar()) number = number *10 + c - 48;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i=0; i!=MAXN; ++i) Deg[i] = 0;
    scan(n);
    scan(m);
    srand(n + m - 7);
    for (int i=0; i!=m; ++i)
    {
        scan(a);
        scan(b);
        a--,--b;
        Deg[max(a,b)]++;
        Graph[a].push_back(make_pair(b,i));
        Graph[b].push_back(make_pair(a,i));
        isBigger[i] = (a > b);
        if (rand()%2)
        {
            Deg[max(a,b)]--;
            Deg[min(a,b)]++;
            Edge[i] = 1;
        }
        else Edge[i] = 0;
    }

    while (true)
    {
        v = 0;
        for (int i=0; i!=n; ++i) if (Deg[i] > Deg[v]) v = i;

        vector <bool> Vis(n, false);
        vector <pair<int,int>> Fath(n); //f.ind - edg.ind
        Fath[v] = make_pair(-1,-1);
        int minV = BFS(v, Vis, Fath);

        if (Deg[v]-1 > Deg[minV])
        {
            Deg[v]--;
            Deg[minV]++;
            while (minV != -1)
            {
                Edge[Fath[minV].second] = (Edge[Fath[minV].second]+1)%2;
                minV = Fath[minV].first;
            }
        }
        else
        {
            cout << Deg[v] << "\n";
            for (int i=0; i!=m; ++i) cout << (Edge[i]+isBigger[i])%2 << "\n";
            return 0;
        }
    }
}

/*
4 7
1 2
1 3
1 4
1 2
2 3
2 4
3 4
*/