#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> edge;
#define pb push_back
vector< pair<int,int> > adjList[1000]; // end node, color - 0 for blank, 1 for blue, 2 for red
vector<edge> edges;
int visited[1000];
int dfs(int c, int prev, int d) {
    /*
    visited[momentalno teme] = 1 ako e del od ciklus so neparen broj na otsecki (2n+1-agolnik) i 2 ako ne e del od ciklus
    */
    if(prev == -1) {
        visited[c] = 1;
    }
    if(visited[c]) {
        if(visited[c] == 1) {
            if(d % 2) return visited[c] = visited[prev] = 1;
            else return visited[c] = visited[prev] = 2;
        } else {
            return visited[c];
        }
    }
    if(prev != -1) visited[c] = visited[prev];
    int ret;
    if(adjList[c].size() > 2) {
        visited[c] = 2;
        for(auto k : adjList[c]) {
            ret = dfs(k.first, c, d+1);
        }
    } else {
        for(auto k : adjList[c]) {
            if(k.first != prev) ret = dfs(k.first, c, d+1);
        }
    }
    return ret;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edges.pb({a,b});
        adjList[a].pb({b, 0});
    }
    for(int i = 0; i < n; i++) {
        memset(visited, 0, sizeof(visited));
        int k = dfs(i, -1, 0);
        cout << i << " " << k << endl;
    }
    return 0;
}