Timus 1303

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

const int INF=1000000000;

struct segment {
    int l,r;
} a[100001];

bool operator < (segment a,segment b) {
    if (a.r==b.r) return (a.l<b.l);
    return (a.r<b.r);
}

bool cmp(int i,int j) {
    return (a[i].l<a[j].l);
}

int dp[5002],pre[5002],seg[5002],ans[5002];
int n,m,z;

int main() {
    //freopen("input.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);
    scanf("%d",&m); m++;
    int l,r;
    scanf("%d %d",&l,&r);
    while (l!=0 || r!=0) {
        a[n].l=l+1; a[n].r=r+1; n++; scanf("%d %d",&l,&r);
    }
    //a[n].l=1; a[n].r=1; n++;
    sort(a,a+n);
    for (int i=1;i<=m;i++) dp[i]=INF;
    for (int i=0;i<n;i++) {
        if (a[i].r<1 || a[i].l>m) continue;
        int ll=max(a[i].l,1);
        int rr=min(a[i].r,m);
        int cur=dp[ll-1];
        //if (cur+1<dp[rr])
            for (int j=rr;j>=ll;j--) {
                if (cur+1<dp[j]) {
                    dp[j]=cur+1;
                    seg[j]=i;
                    pre[j]=ll-1;
                } //else break;
            }
    }
    if (dp[m]==INF) {printf("No solution"); return 0; }
    for (int i=m;i!=0;i=pre[i]) ans[z++]=seg[i];
    sort(ans,ans+z);
    printf("%d\n",z);
    for (int i=0;i<z;i++) {
        printf ("%d %d\n",a[ans[i]].l-1,a[ans[i]].r-1);
    }
    return 0;
}