#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;

struct EmptyType {};

// Remember to Init() after adding the edges
template<typename EdgeAttributes = EmptyType>
class Graph {
  private:
    Graph();
    struct Edge : public EdgeAttributes {
        int from, to;
        Edge() { }
        Edge(const int _from, const int _to, const EdgeAttributes& attr) : EdgeAttributes(attr), from(_from), to(_to) { }
    };
    
    template<typename T>
    struct Range {
        struct Iterator {
            T& operator *() const { return *iter; }
            bool operator !=(const Iterator& rhs) const { return iter != rhs.iter; }
            void operator ++() { ++iter; }
            T* operator +(int i) const { return iter + i; }
            size_t operator -(const Iterator& rhs) const { return iter - rhs.iter; }
            T* iter;
        };
        
        Range(T* _first, T* _last) : first({_first}), last({_last}) { }
        T operator[] (const int i) { return *(first + i); }
        size_t size() const { return last - first; }
        Iterator& begin() { return first; }
        Iterator& end() { return last; }
        Iterator first, last;
    };
  public:
    explicit Graph(const int N, const int M=0) : n_(N), offset_(N + 1) {
        if (M > 0) { in_.reserve(M); }
    } 
    
    void AddEdge(int x, int y, const EdgeAttributes attr = EdgeAttributes()) { in_.emplace_back(x, y, attr); }
    
    virtual void Init() {
        ReorderEdges();
    }
    
    size_t size() const {
        return (size_t)n_;
    }

    Range<int> operator [](const int u) { 
        return Range<int>(&edges_[offset_[u]], &edges_[offset_[u + 1]]); 
    }

    int node(const int edge_idx) const {
        return in_[edge_idx].to;
    }

    EdgeAttributes value(const int edge_idx) const {
        return in_[edge_idx];
    }
  protected:
    void ReorderEdges() {
        edges_.resize(in_.size());
        for (auto&& e : in_) { offset_[e.from] += 1; }
        for (int i = 1; i <= n_; i += 1) { 
            offset_[i] += offset_[i - 1]; 
        }
        for (size_t i = 0; i < in_.size(); i += 1) {
            edges_[--offset_[in_[i].from]] = i; 
        }
    }
    
    int n_;
    vector<int> offset_, edges_;
    vector<Edge> in_;
};

class BipartiteGraph : public Graph<EmptyType> {
  public:
    explicit BipartiteGraph(const int N, const int M=0) : Graph<EmptyType>(N, M), side_(N), pair_(N, -1) { }

    virtual void Init() {
        ReorderEdges();
        
        vector<bool> marked(n_);
        function<void(int, bool)> Dfs = [&](int node, bool where) {
            marked[node] = true;
            side_[node] = where;

            for (auto&& edge : (*this)[node]) {
                const int to = (*this).node(edge);
                if (not marked[to]) {
                    Dfs(to, where ^ 1);
                }
            }
        };

        for (int i = 0; i < n_; i += 1) {
            if (not marked[i]) {
                Dfs(i, 0);
            }
        }
    }

    int MaxMatching() {
        vector<bool> marked(n_);
        function<bool(int)> PairUp = [&](int node) {
            if (marked[node]) {
                return false;
            }
            
            marked[node] = true;
            for (auto&& edge : (*this)[node]) {
                const int to = (*this).node(edge);
                if (pair_[to] == -1) {
                    pair_[node] = to;
                    pair_[to] = node;
                    return true;
                }
            }

            for (auto&& edge : (*this)[node]) {
                const int to = (*this).node(edge);
                if (PairUp(pair_[to])) {
                    pair_[node] = to;
                    pair_[to] = node;
                    return true;
                }
            }
            return false;
        };

        bool pushed;
        int matching = 0;
        do {
            fill(marked.begin(), marked.end(), false);
            pushed = false;
            for (int i = 0; i < n_; i += 1) {
                if (side_[i] == 0 and pair_[i] == -1) {
                    if (PairUp(i)) {
                        pushed = true;
                        matching += 1;
                    }
                }
            }
        } while (pushed);
        return matching;
    }

    vector<pair<int, int>> GetMatching() {
        int matching = MaxMatching();
        vector<pair<int, int>> solution;
        solution.reserve(matching);

        for (int i = 0; i < n_; i += 1) {
            if (side_[i] == 0 and pair_[i] != -1) {
                solution.emplace_back(i, pair_[i]);
            }
        }
        return solution;
    }

    vector<int> MinimumVertexCover() { // = max_matching
        const int matching = MaxMatching();

        auto&& selected = SelectNodes();
        vector<int> solution;
        solution.reserve(matching);

        for (int i = 0; i < n_; i += 1) {
            if (selected[i]) {
                solution.push_back(i);
            }
        }
        return solution;
    }

    vector<int> MaximumIndependentSet() { // = n - max_matching
        const int matching = MaxMatching();

        auto&& selected = SelectNodes();
        vector<int> solution;
        solution.reserve(n_ - matching);

        for (int i = 0; i < n_; i += 1) {
            if (not selected[i]) {
                solution.push_back(i);
            }
        }
        return solution;
    }
  private:
     vector<bool> SelectNodes() {
        vector<bool> selected(n_);
        for (int i = 0; i < n_; i += 1) {
            if (side_[i] == 0 and pair_[i] != -1) {
                selected[i] = true;
            }
        }

        function<void(int)> Cover = [&](int node) {
            for (auto&& edge : (*this)[node]) {
                const int to = (*this).node(edge);
                if (not selected[to]) {
                    selected[to] = true;
                    selected[pair_[to]] = true;
                    Cover(pair_[to]);
                }
            }
        };

        for (int i = 0; i < n_; i += 1) {
            if (side_[i] == 0 and pair_[i] == -1) {
                Cover(i);
            }
        }
        return selected;
     }

     vector<bool> side_;
     vector<int> pair_;
};

int main() {
    ifstream cin("felinare.in");
    ofstream cout("felinare.out");

    int n, m; cin >> n >> m;
    BipartiteGraph G(2 * n, m);
    for (int i = 0; i < m; i += 1) {
        int x, y; cin >> x >> y; x -= 1; y -= 1;
        G.AddEdge(x, n + y);
    }
    G.Init();
    
    vector<int> mis = G.MaximumIndependentSet();
    cout << mis.size() << '\n';

    sort(mis.begin(), mis.end());
    for (int i = 0; i < n; i += 1) {
        cout << (binary_search(mis.begin(), mis.end(), i)
                    | binary_search(mis.begin(), mis.end(), i + n) << 1) << '\n';
    }
    return 0;
}