BỘ GHÉP TỐI ĐA

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 3e4 + 5;
constexpr int block = 180;
struct Edge
{
    int u, v;
    ll c;
    Edge() {}
    Edge(int u, int v, ll c)
    {
        this->u = u;
        this->v = v;
        this->c = c;
    }
};

struct Dinic
{
    const ll Inf = 1e17;
    vector<vector<int>> adj;
    vector<vector<int>::iterator> cur;
    vector<Edge> s;
    vector<int> h;
    int sink, t;
    int n;
    Dinic(int n = 0)
    {
        this->n = n;
        adj.resize(n + 1);
        h.resize(n + 1);
        cur.resize(n + 1);
        s.reserve(n);
    }
    void AddEdge(int u, int v, ll c)
    {
        s.emplace_back(u, v, c);
        adj[u].push_back(s.size() - 1);
        s.emplace_back(v, u, 0);
        adj[v].push_back(s.size() - 1);
    }
    bool BFS()
    {
        fill(h.begin(), h.end(), n + 2);
        queue<int> pq;
        h[t] = 0;
        pq.emplace(t);
        while (pq.size())
        {
            int c = pq.front();
            pq.pop();
            for (auto i : adj[c])
                if (h[s[i ^ 1].u] == n + 2 && s[i ^ 1].c != 0)
                {
                    h[s[i ^ 1].u] = h[c] + 1;
                    if (s[i ^ 1].u == sink)
                        return true;
                    pq.emplace(s[i ^ 1].u);
                }
        }
        return false;
    }
    ll DFS(int v, ll flowin)
    {
        if (v == t)
            return flowin;
        ll flowout = 0;
        for (; cur[v] != adj[v].end(); ++cur[v])
        {
            int i = *cur[v];
            if (h[s[i].v] + 1 != h[v] || s[i].c == 0)
                continue;
            ll q = DFS(s[i].v, min(flowin, s[i].c));
            flowout += q;
            if (flowin != Inf)
                flowin -= q;
            s[i].c -= q;
            s[i ^ 1].c += q;
            if (flowin == 0)
                break;
        }
        return flowout;
    }
    void BlockFlow(ll &flow)
    {
        for (int i = 1; i <= n; ++i)
            cur[i] = adj[i].begin();
        flow += DFS(sink, Inf);
    }
    ll MaxFlow(int s, int t)
    {
        this->sink = s;
        this->t = t;
        ll flow = 0;
        while (BFS())
            BlockFlow(flow);
        return flow;
    }
};

int m, n, p, q, in[N], beg[N], en[N];
int l[N], r[N], id[N];
vector<int> x[block], y[block];

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
        cin >> l[i] >> r[i];

    p = m;
    q = n;
}

void Solve()
{

    for (int i = 1; i <= q; ++i)
    {
        in[i] = i / block + 1;
        if (!beg[in[i]])
            beg[in[i]] = i;
        en[in[i]] = i;
    }

    int source = p + q + block + 1,
        sink = p + q + block + 2;

    /*
        X: 1, 2, ..., p
        Y: p + 1, p + 2, ..., p + q
        sqrt: p + q + 1, p + q + 2, ..., p + q + block
        source: p + q + block + 1,
        sink: p + q + block + 2
    */

    /// ----- Add Edge -----
    Dinic f(p + q + block + 5);

    /// source -> X

    for (int i = 1; i <= p; ++i)
        f.AddEdge(source, i, 1);

    /// X->Y

    for (int i = 1; i <= p; ++i)
        for (int j = 1; j <= in[q]; ++j)
            if ((beg[j] <= l[i] && en[j] > l[i]) || (en[j] >= r[i] && beg[j] < r[i]))
            {
                for (int t = beg[j]; t <= en[j]; ++t)
                    if (t <= l[i] || t >= r[i])
                        f.AddEdge(i, p + t, 1);
            }
            else if (beg[j] >= r[i] || en[j] <= l[i])
                f.AddEdge(i, p + q + j, 1);

    for (int i = 1; i <= q; ++i)
        f.AddEdge(p + q + in[i], p + i, 1);

    /// Y -> sink

    for (int i = 1; i <= q; ++i)
        f.AddEdge(p + i, sink, 1);

    /// ----- Print -----

    cout << f.MaxFlow(source, sink) << "\n";

    for (int i = 0; i < (int)f.s.size(); i += 2)
        if (f.s[i].v > p + q) // sink or sqrt
        {
            if (f.s[i].v != p + q + block + 2) // Just sqrt
                for (int j = 0; j < f.s[i ^ 1].c; ++j)
                    x[f.s[i].v - p - q].emplace_back(f.s[i].u);
        }
        else if (f.s[i].v > p) // Y
        {
            if (f.s[i].u <= p) // Cung nay la tu X->y
            {
                for (int j = 0; j < f.s[i ^ 1].c; ++j)
                    cout << f.s[i].u << " " << f.s[i].v - p << "\n";
            }
            else //  Cung nay la tu sqrt->Y
            {
                for (int j = 0; j < f.s[i ^ 1].c; ++j)
                    y[f.s[i].u - p - q].emplace_back(f.s[i].v - p);
            }
        }

    for (int i = 1; i <= in[q]; ++i) // Noi bat ki tu X->sqrt->Y
        while (!x[i].empty())
        {
            cout << x[i].back() << " " << y[i].back() << "\n";
            x[i].pop_back();
            y[i].pop_back();
        }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Read();
    Solve();
}