#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<set>
#include <utility>
#include <iterator>
#define INT long long int
using namespace std;

char in[100], out[100];
INT T, n, m, ans = 1, b[110];

bool compare(pair<int, int> x, pair<int, int> y){
    return x.second < y.second;
}

int main(){
    int n, i,  t, m,j,a1,b1,k;
	for(int I = 1; I<=40; I++){
		sprintf(in,".%d.in",I);
        freopen(in,"w",stdout);
        n = I * 2500;
        k = rand()%100+1;
        printf("%d %d\n", k, n);
        vector<pair<int, int> > a(n);

        for(i=0;i<n;i++){
            a1 = (rand()*1000+ rand())%86401;
            b1 = (rand()*1000+ rand())%86401;
            if(a1>b1){
                t = a1;
                a1 = b1;
                b1 = t;
            }
            printf("%d %d\n",a1,b1);
            a[i] = {a1,b1};
        }
        sort(a.begin(), a.end(), compare);

        vector<int> room(k, -1);

        int ans = 0;
        pair<int, int> pr;
        for(int i = 0; i < n; ++i){
            pr = {-2, -1};

            for(int j = 0; j < k; ++j){
                if(a[i].first >= room[j]){
                    pr = max(pr, {room[j], j});
                }
            }

            if(pr.first != -2){
                ++ans;

                room[pr.second] = a[i].second;
            }
        }
		sprintf(in,".%d.out",I);
        freopen(in,"w",stdout);
        printf("%d",ans);
	}
}