ShoeBox

#include <bits/stdc++.h>

using namespace std;

ifstream fin("shoebox.in");
ofstream fout("shoebox.out");

int n, cerinta;

struct Cutie {
    int L, l;
};

bool Incape(Cutie A, Cutie B)
{
    return A.L <= B.L && A.l <= B.l;
}

bool comp(Cutie A, Cutie B)
{
    return A.L < B.L || (A.L == B.L && A.l < B.l);
}

vector < Cutie > Cutii;

vector < stack < Cutie > > v;

stack < Cutie > a;

int main()
{
    fin >> cerinta >> n;

    for (int i = 1; i <= n; i++)
    {
        int L, l;

        fin >> L >> l;

        Cutii.push_back({max(L, l), min(L, l)});
    }

    sort(Cutii.begin(), Cutii.end(), comp);

    for (int i = 0; i < Cutii.size(); i++)
    {
        bool oke = false;

        for (int j = 0; j < v.size(); j++)
        {
            if (Incape(v[j].top(), Cutii[i]))
            {
                v[j].push(Cutii[i]);
                oke = true;
            }
        }

        if (!oke)
        {
            stack < Cutie > a;
            a.push(Cutii[i]);
            v.push_back(a);
        }
    }


    if (cerinta == 1)
    {
        size_t maxim = 0;

        for (int i = 0; i < v.size(); i++)
            maxim = max(maxim, v[i].size());

        fout << maxim;

    }
    else
        fout << v.size();


    fin.close();
    fout.close();
    return 0;
}


/*#include <bits/stdc++.h>

using namespace std;

ifstream fin("shoebox.in");
ofstream fout("shoebox.out");

int n, cerinta;

struct Cutie {
    int L, l;
};

bool Incape(Cutie A, Cutie B)
{
    return A.L <= B.L && A.l <= B.l;
}

bool comp(Cutie A, Cutie B)
{
    return A.L < B.L || (A.L == B.L && A.l < B.l);
}

vector < Cutie > Cutii;
vector < int > l[1005];

bitset < 1005 > viz;

queue < pair < int, int > > q;

int maxim = 1, rez = 0;

void BFS(int nod)
{
    int timp = 1;

    q.push({nod, timp});
    viz[nod] = 1;

    while (!q.empty())
    {
        nod = q.front().first;
        timp = q.front().second;
        q.pop();

        maxim = max(maxim, timp);

        for (int vecin : l[nod])
            if (!viz[vecin])
            {
                q.push({vecin, timp + 1});
                viz[vecin] = 1;
            }
    }
}

stack < int > stk;

void DFS(int nod)
{
    viz[nod] = 1;
}

int main()
{
    fin >> cerinta >> n;

    for (int i = 1; i <= n; i++)
    {
        int L, l;

        fin >> L >> l;

        Cutii.push_back({max(L, l), min(L, l)});
    }

    sort(Cutii.begin(), Cutii.end(), comp);

    for (int i = 0; i < Cutii.size() - 1; i++)
        for (int j = i + 1; j < Cutii.size(); j++)
            if (Incape(Cutii[j], Cutii[i]))
                l[i + 1].push_back(j + 1);


    if (cerinta == 1)
    {
        for (int i = 1; i <= n; i++)
            if (!viz[i])
                BFS(i);

        fout << maxim;
    }
    else
    {
        for (int i = 1; i <= n; i++)
            if (!viz[i])
            {
                rez++;
                DFS(i);
            }

        fout << rez;
    }

    fin.close();
    fout.close();
    return 0;
}
*/