#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <stack>
#include <map>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <cmath>

using namespace std;

istream & operator >> (istream & in, vector<int> & v)
{
    string str;
    getline(in,str);
    stringstream stream(str);
    int tmp;
    while(stream >> tmp)
        v.push_back(tmp);
    return in;
}

ostream & operator << (ostream & out, vector<int> const & v)
{
    for(int el: v)
        out << el << ' ';
    return out;
}

int KolVoRod(map<string, string> Roditel, string el)
{
    int k = -1;
    while (1 == 1)
    {
        if (Roditel.find(el) != Roditel.end()){
            el = Roditel[el];
            ++k;
        }
        else
            break;
    }
    return k;
}

int main()
{
    int K, N;
    cin >> K >> N;
    vector<int> vec(N), vec2(N), vec3(N);
    set<int> s;
    multiset<pair<int, int>> ms;
    for (auto i = 0; i < N; ++i)
        cin >> vec[i] >> vec2[i];
    for (auto i = 1; i <= K; ++i)
        s.insert(i);
    for (auto i = 0; i < N; ++i)
    {
        for (auto j = ms.begin(); j != ms.end();)
            if (j->first < vec[i])
            {
                for (auto el = j; el != ms.end() & el->first == j->first; ++el)
                    s.insert(el->second);
                j = ms.erase(j);
            }
            else
                break;
        if (s.size() == 0 )
            return (cout << 0 << " " << i + 1, 0);
        vec3[i] = *s.begin();
        ms.insert({vec2[i], *s.begin()});
        s.erase(*s.begin());
    }
    for (auto el: vec3){
        cout << el << endl;
    }
    return 0;
}