#pragma optimization_level 3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <stack>
#include <assert.h>
#include <list>
#include <time.h>
#include <memory>
#include <chrono>
using namespace std;
//
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
//#define cin in
//#define cout out
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define F first
#define S second
#define ms multiset
#define pb push_back
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define PI acos(-1.0)
//#define sort(a, b) sort(a.begin(), a.end(), b())
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("input.txt");
ofstream out("output.txt");

struct Q {
    int l, r, pos;
};

vector<Q> f_arcs;
vector<int> ans;
int n, m;

bool check() {
    //1/-1 - '0', 2/-2 - '1'
    //{pos, -2, -1/+1, +2}
    vector<pii> line;
    for (int i = 0; i < m; i++) {
        Q q = f_arcs[i];
        int t = (ans[i] == 0 ? 1 : 2);
        if (q.l > q.r)
            line.push_back({ 1, t });
        line.push_back({ q.l, t });
        line.push_back({ q.r + 1, -t });
    }
    sort(line.begin(), line.end());
    int cnt0 = 0, cnt1 = 0;
    for (int i = 1, p = 0; i <= n; i++) {
        while (p < line.size() && line[p].first == i) {
            if (abs(line[p].second) == 2)
                cnt1 += 0.5 * line[p].second;
            else
                cnt0 += line[p].second;
            p++;
        }
        if (cnt0 == 0 || cnt1 == 0) return 0;
    }
    return 1;
}

bool is_bit(int a, int p) {
    return (a >> p) % 2;
}

bool solve() {
    for (int mask = 0; mask < (1 << m); mask++) {
        for (int i = 0; i < m; i++)
            ans[i] = is_bit(mask, i);
        if (check()) {
           // for (int x : ans)
                //cout << x;
           // cout << '\n';
            return 1;
        }
    }
    return 0;
}

vector<Q> arcs;

void gen() {
    n = rand() % 5 + 2;
    m = rand() % 5 + 2;
    arcs.clear();
    f_arcs.clear();
    for (int i = 0; i < m; i++)
        arcs.push_back({ rand() % n + 1, rand() % n + 1, i });
}

bool my_sol() {
    int b_dist = -1, b_num = -1;
    for (int i = 0; i < m; i++) {
        int l = arcs[i].l, r = arcs[i].r;
        int dist = (l > r ? n - l + r : r - l);
        if (dist > b_dist) {
            b_dist = dist;
            b_num = i;
        }
    }
    ans.resize(m, 0);

    ////////
    int d = arcs[b_num].l;
    for (Q& q : arcs) {
        q.l = ((q.l - d + n) % n) + 1;
        q.r = ((q.r - d + n) % n) + 1;
    }
    //
    f_arcs = arcs;

    vector<Q> spec;

    for (Q q : arcs) {
        if (q.l > q.r)
            spec.push_back(q);
    }

    int m1 = m;
    {
        int p = 0;
        for (int i = 0; i < m; i++) {
            if (arcs[i].l <= arcs[i].r)
                arcs[p++] = arcs[i];
        }
        arcs.resize(p);
        m1 = p;
    }
    //
    sort(arcs.begin(), arcs.end(), [&](const Q a, const Q b) {return a.l < b.l; });

    for (int ch = -1; ch < (int)spec.size(); ch++) {
        fill(ans.begin(), ans.end(), 0);
        ans[b_num] = 1;

        int p[2] = { 0, 0 }, fin[2] = { n, n };
        for (int i = 0; i < spec.size(); i++) {
            ans[spec[i].pos] = (i == ch);
            p[i == ch] = max(spec[i].r, p[i == ch]);
            fin[i == ch] = min(spec[i].l - 1, fin[i == ch]);
        }

        p[1] = max(p[1], f_arcs[b_num].r);

        int vp = 0;
        //{r, num}
        pq<pii> q;
        while (p[0] < fin[0] || p[1] < fin[1]) {
            int k;
            if (p[0] >= fin[0]) k = 1;
            else if (p[1] >= fin[1]) k = 0;
            else k = (p[0] <= p[1] ? 0 : 1);

            while (vp < m1 && arcs[vp].l <= p[k] + 1) {
                if (arcs[vp].pos != b_num)
                    q.push({ arcs[vp].r, arcs[vp].pos });
                vp++;
            }

            if (q.empty()) break;

            pii x;
            if (q.size() >= 2) {
                pii tmp = q.top();
                q.pop();
                x = q.top();
                if (x.first >= fin[k]) {
                    q.pop();
                    q.push(tmp);
                    ans[x.second] = k;
                    p[k] = x.first;
                    continue;
                }
                else
                    q.push(tmp);
            }

            if (p[!k] < fin[!k] && fin[!k] > fin[k] && q.top().first >= fin[!k] && q.size() >= 2) {
                if (q.size() == 1) break;
                pii tmp = q.top();
                q.pop();
                x = q.top();
                q.pop();
                q.push(tmp);
            }
            else {
                x = q.top();
                q.pop();
            }

            ans[x.second] = k;
            p[k] = x.first;
        }
        if (p[0] >= fin[0] && p[1] >= fin[1])
            return 1;
    }
    return 0;
}

int main() {
    srand(time(0));
    for (int cnt = 0;; cnt++) {
        gen();
        if (cnt % 10000 == 0)
            cout << "=";

        if (!my_sol() && solve()) {
            cout << "\n";
            cout << n << ' ' << m << '\n';
            for (Q q : f_arcs)
                cout << q.l << ' ' << q.r << '\n';
            return 0;
        }
    }
}