#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

#define mp make_pair
#define N int(5e5 + 5)
#define INF int(1e9)

int tree[4 * N], k, n, sz = 1, res[N];

void build() {
    while (sz < k) sz *= 2;
    for (int i = sz; i < sz + k; i++)
        tree[i] = i - sz + 1;
    for (int i = sz + k; i < sz * 2; i++)
        tree[i] = INF;
    for (int i = sz - 1; i; i--)
        tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}

void update(int v, int val) {
    v += sz - 1;
    tree[v] = val;
    v /= 2;
    while (v) {
        tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
        v /= 2;
    }
}

struct train {
    int timer, ch, num;

    train() {}

    train(int a, int b, int c) {
        timer = a, ch = b, num = c;
    }
};

bool operator < (train a, train b) {
    if (a.timer == b.timer)
        return a.ch < b.ch;
    return a.timer < b.timer;
}

train a[2 * N];

int main() {
    freopen("trains.in", "r", stdin);
    freopen("trains.out", "w", stdout);

    while (scanf("%d %d ", &k, &n) != -1) {
        build();

        for (int i = 0; i < n; i++) {
            int in, out;
            scanf("%d %d ", &in, &out);
            a[i * 2] = train(in, 0, i + 1);
            a[i * 2 + 1] = train(out, 1, i + 1);
        }

        sort(a, a + 2 * n);

        bool ex = false;

        for (int i = 0; i < 2 * n; i++) {
            if (a[i].ch) {
                update(res[ a[i].num ], res[ a[i].num ]);
            }
            else {
                if (tree[1] == INF) {
                    printf("0 %d\n", a[i].num);
                    ex = true;
                    break;
                }
                res[ a[i].num ] = tree[1];
                update(tree[1], INF);
            }
        }

        if (ex) continue;

        for (int i = 1; i <= n; i++)
            printf("%d\n", res[i]);
    }

    return 0;
}