stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct robot

{

	int x,y; 

}r[200005];

int left1[200005];

int right1[200005];

int res[200005];

int cmp(struct robot a,struct robot b)

{

	return a.x<b.x;

}

int main(void)

{

	int n;

	int m;

	while(~scanf("%d %d",&n,&m))

	{

		for(int i=0;i<=n;i++)

		{

			left1[i]=right1[i]=i;

		}

		memset(res,0,sizeof(res));

		for(int i=1;i<=m;i++)

		{

			scanf("%d %d",&r[i].x,&r[i].y);

		}

		sort(r+1,r+m+1,cmp);

		for(int i=1;i<=m;i++)

		{

			int xx=r[i].y;

			left1[xx]=left1[xx+1]=min(left1[xx],left1[xx+1]);

			right1[xx]=right1[xx+1]=max(right1[xx],right1[xx+1]);

		}

		cout<<right1[1]-left1[1]+1;

		for(int i=2;i<=n;i++)

		{

			cout<<" "<<right1[i]-left1[i]+1;

		}

		cout<<endl;

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.9036965482290122x):
#include<bits/stdc++.h>

#define ll long long

#define MAX  2147483647

#define fi first

#define se second

#define mid (l+r>>1)

#define fo(i,a,b) for(int i=(a);i<=(b);++i)

#define fodown(i,a,b) for(int i=(a);i>=(b);i--)

using namespace std;

int n,m;

pair<int,int> num[200001];

struct node{

	int x,y;

}a[100001];

int read()

{

   int x=0,tmp=1;

   char ch=getchar();

   while(ch<'0' || ch>'9' ) { if(ch=='-') tmp=-1;ch=getchar();}

   while(ch>='0'&& ch<='9') { x = x * 10+ ch-'0';ch=getchar();}

   return x*tmp;

}

int cmp(node a,node b)

{

    return a.x<b.x;

}

int main()

{

  // freopen(" .in","r",stdin);

  // freopen(" .out","w",stdout);

  n=read();

  m=read();

  fo(i,1,m)

  {

  	 a[i].x=read();

  	 a[i].y=read();

  }

  sort(a+1,a+m+1,cmp);

  fo(i,1,n)

  num[i].fi=i,num[i].se=i;

  int y;

  for(int i=1;i<=m;i++){

  	    y= a[i].y;

        num[y].fi = num[y+1].fi = min(num[y].fi, num[y+1].fi);

        num[y].se = num[y+1].se = max(num[y].se, num[y+1].se);

  }

  fo(i,1,n-1)

  {

    printf("%d ",num[i].se-num[i].fi+1);	

  }

  cout<<num[n].se-num[n].fi+1<<endl;

   return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

vector<pair<int,int> >v;

int ans[N],a[N];

int main()

{

    int n,m,i;

    cin>>n>>m;

    for(i=1;i<=n;i++)ans[i]=1;

    for(i=0;i<m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        v.push_back(make_pair(x,y));

    }

    sort(v.begin(),v.end());

    memset(a,0,sizeof a);

    for(auto x:v)

    {

        int y=x.second;

        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];

        a[y]=ans[y];

    }

    cout<<ans[1];

    for(i=2;i<=n;i++)printf(" %d",ans[i]);

    cout<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8120500707868303x):
#include<bits/stdc++.h>

using namespace std;

int n,m;

struct jxb{

	int x,y;

};

bool cmp(jxb b,jxb c){

	return b.x<c.x;

}

jxb a[100010];

int ans[200010];

map<int,int>mp;

map<int,int>f;

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	sort(a+1,a+m+1,cmp);

	for(int i=1;i<=n;i++) ans[i]=1;

	for(int i=1;i<=m;i++){

		if(mp[a[i].y]==1){

			ans[a[i].y]=ans[a[i].y+1]=ans[a[i].y]+ans[a[i].y+1]-f[a[i].y];

			f[a[i].y]=ans[a[i].y];

		}else{

			mp[a[i].y]=1;

			ans[a[i].y]+=ans[a[i].y+1];

			ans[a[i].y+1]=ans[a[i].y];

			f[a[i].y]=ans[a[i].y];

		}

	}

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

		printf("%d",ans[i]);

		if(i!=n) printf(" ");

	}

	printf("\n");

	return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct robot

{

	int x,y; 

}r[200005];

int left1[200005];

int right1[200005];

int res[200005];

int cmp(struct robot a,struct robot b)

{

	return a.x<b.x;

}

int main(void)

{

	int n;

	int m;

	while(~scanf("%d %d",&n,&m))

	{

		for(int i=0;i<=n;i++)

		{

			left1[i]=right1[i]=i;

		}

		memset(res,0,sizeof(res));

		for(int i=1;i<=m;i++)

		{

			scanf("%d %d",&r[i].x,&r[i].y);

		}

		sort(r+1,r+m+1,cmp);

		for(int i=1;i<=m;i++)

		{

			int xx=r[i].y;

			left1[xx]=left1[xx+1]=min(left1[xx],left1[xx+1]);

			right1[xx]=right1[xx+1]=max(right1[xx],right1[xx+1]);

		}

		cout<<right1[1]-left1[1]+1;

		for(int i=2;i<=n;i++)

		{

			cout<<" "<<right1[i]-left1[i]+1;

		}

		cout<<endl;

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.8885252456176047x):
#include<bits/stdc++.h>

using namespace std;

int n,m;

struct jxb{

	int x,y;

};

bool cmp(jxb b,jxb c){

	return b.x<c.x;

}

jxb a[100010];

int ans[200010];

map<int,int>mp;

map<int,int>f;

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	sort(a+1,a+m+1,cmp);

	for(int i=1;i<=n;i++) ans[i]=1;

	for(int i=1;i<=m;i++){

		if(mp[a[i].y]==1){

			ans[a[i].y]=ans[a[i].y+1]=ans[a[i].y]+ans[a[i].y+1]-f[a[i].y];

			f[a[i].y]=ans[a[i].y];

		}else{

			mp[a[i].y]=1;

			ans[a[i].y]+=ans[a[i].y+1];

			ans[a[i].y+1]=ans[a[i].y];

			f[a[i].y]=ans[a[i].y];

		}

	}

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

		printf("%d",ans[i]);

		if(i!=n) printf(" ");

	}

	printf("\n");

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

vector<pair<int,int> >v;

int ans[N],a[N];

int main()

{

    int n,m,i;

    cin>>n>>m;

    for(i=1;i<=n;i++)ans[i]=1;

    for(i=0;i<m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        v.push_back(make_pair(x,y));

    }

    sort(v.begin(),v.end());

    memset(a,0,sizeof a);

    for(auto x:v)

    {

        int y=x.second;

        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];

        a[y]=ans[y];

    }

    cout<<ans[1];

    for(i=2;i<=n;i++)printf(" %d",ans[i]);

    cout<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8181565310704886x):
#include<bits/stdc++.h>



using namespace std;



const int maxn=2*100005;

const int maxm=100005;



struct point{

	int x,y;

}a[maxn];



int ans[maxn];

int num[maxn];



bool cmp(point a,point b)

{

	return a.x<b.x;

}



int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	sort(a+1,a+m+1,cmp);

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

		ans[i]++;

	}

	for(int i=1;i<=m;i++){

		int t=ans[a[i].y];

		ans[a[i].y]+=ans[a[i].y+1]-num[a[i].y];

		ans[a[i].y+1]+=t-num[a[i].y];

		num[a[i].y]=ans[a[i].y];

	}

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

		if(i!=n)

		printf("%d ",ans[i]);

		else printf("%d\n",ans[i]);

	}

	return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct robot

{

	int x,y; 

}r[200005];

int left1[200005];

int right1[200005];

int res[200005];

int cmp(struct robot a,struct robot b)

{

	return a.x<b.x;

}

int main(void)

{

	int n;

	int m;

	while(~scanf("%d %d",&n,&m))

	{

		for(int i=0;i<=n;i++)

		{

			left1[i]=right1[i]=i;

		}

		memset(res,0,sizeof(res));

		for(int i=1;i<=m;i++)

		{

			scanf("%d %d",&r[i].x,&r[i].y);

		}

		sort(r+1,r+m+1,cmp);

		for(int i=1;i<=m;i++)

		{

			int xx=r[i].y;

			left1[xx]=left1[xx+1]=min(left1[xx],left1[xx+1]);

			right1[xx]=right1[xx+1]=max(right1[xx],right1[xx+1]);

		}

		cout<<right1[1]-left1[1]+1;

		for(int i=2;i<=n;i++)

		{

			cout<<" "<<right1[i]-left1[i]+1;

		}

		cout<<endl;

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.8948894209751004x):
#include<bits/stdc++.h>



using namespace std;



const int maxn=2*100005;

const int maxm=100005;



struct point{

	int x,y;

}a[maxn];



int ans[maxn];

int num[maxn];



bool cmp(point a,point b)

{

	return a.x<b.x;

}



int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	sort(a+1,a+m+1,cmp);

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

		ans[i]++;

	}

	for(int i=1;i<=m;i++){

		int t=ans[a[i].y];

		ans[a[i].y]+=ans[a[i].y+1]-num[a[i].y];

		ans[a[i].y+1]+=t-num[a[i].y];

		num[a[i].y]=ans[a[i].y];

	}

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

		if(i!=n)

		printf("%d ",ans[i]);

		else printf("%d\n",ans[i]);

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

vector<pair<int,int> >v;

int ans[N],a[N];

int main()

{

    int n,m,i;

    cin>>n>>m;

    for(i=1;i<=n;i++)ans[i]=1;

    for(i=0;i<m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        v.push_back(make_pair(x,y));

    }

    sort(v.begin(),v.end());

    memset(a,0,sizeof a);

    for(auto x:v)

    {

        int y=x.second;

        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];

        a[y]=ans[y];

    }

    cout<<ans[1];

    for(i=2;i<=n;i++)printf(" %d",ans[i]);

    cout<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8325083597465175x):
#include <iostream>

#include <cstring>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <cstdio>

#include <cmath>

#include <stack>

typedef long long ll;

#define INF 0x3f3f3f3f



using namespace std;

struct Node {

	int x, y;



};

bool cmp(Node n1, Node n2) {

	return n1.x < n2.x;

}



ll dp[200000 + 10];

Node node[100000 + 10];

ll pre[200000 + 10][2];

void solve() {

	int n, m;

	scanf("%d%d", &n, &m);

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

			dp[i] = dp[i] = 1;

	}

	for(int i = 0; i < m; i++) {

		scanf("%d%d", &node[i].x, &node[i].y);

	}

	

	sort(node, node + m, cmp);

	

	for(int i = 0; i < m; i++) {

		ll pre1 = dp[node[i].y], pre2 = dp[node[i].y + 1];

		dp[node[i].y] += pre2 - pre[node[i].y][1];

		dp[node[i].y + 1] += pre1 - pre[node[i].y + 1][0];

		

		pre[node[i].y][1] = dp[node[i].y];

		pre[node[i].y + 1][0] = dp[node[i].y + 1];

		

	}

	

	printf("%lld", dp[1]);

	for(int i = 2; i <= n; i++) {

		printf(" %lld", dp[i]);

	}

	printf("\n");

		

}

int main(int argc, char *argv[]) {

	solve();

}
// Slower C++ solution:
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct robot

{

	int x,y; 

}r[200005];

int left1[200005];

int right1[200005];

int res[200005];

int cmp(struct robot a,struct robot b)

{

	return a.x<b.x;

}

int main(void)

{

	int n;

	int m;

	while(~scanf("%d %d",&n,&m))

	{

		for(int i=0;i<=n;i++)

		{

			left1[i]=right1[i]=i;

		}

		memset(res,0,sizeof(res));

		for(int i=1;i<=m;i++)

		{

			scanf("%d %d",&r[i].x,&r[i].y);

		}

		sort(r+1,r+m+1,cmp);

		for(int i=1;i<=m;i++)

		{

			int xx=r[i].y;

			left1[xx]=left1[xx+1]=min(left1[xx],left1[xx+1]);

			right1[xx]=right1[xx+1]=max(right1[xx],right1[xx+1]);

		}

		cout<<right1[1]-left1[1]+1;

		for(int i=2;i<=n;i++)

		{

			cout<<" "<<right1[i]-left1[i]+1;

		}

		cout<<endl;

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.9098469495845003x):
#include <iostream>

#include <cstring>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <cstdio>

#include <cmath>

#include <stack>

typedef long long ll;

#define INF 0x3f3f3f3f



using namespace std;

struct Node {

	int x, y;



};

bool cmp(Node n1, Node n2) {

	return n1.x < n2.x;

}



ll dp[200000 + 10];

Node node[100000 + 10];

ll pre[200000 + 10][2];

void solve() {

	int n, m;

	scanf("%d%d", &n, &m);

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

			dp[i] = dp[i] = 1;

	}

	for(int i = 0; i < m; i++) {

		scanf("%d%d", &node[i].x, &node[i].y);

	}

	

	sort(node, node + m, cmp);

	

	for(int i = 0; i < m; i++) {

		ll pre1 = dp[node[i].y], pre2 = dp[node[i].y + 1];

		dp[node[i].y] += pre2 - pre[node[i].y][1];

		dp[node[i].y + 1] += pre1 - pre[node[i].y + 1][0];

		

		pre[node[i].y][1] = dp[node[i].y];

		pre[node[i].y + 1][0] = dp[node[i].y + 1];

		

	}

	

	printf("%lld", dp[1]);

	for(int i = 2; i <= n; i++) {

		printf(" %lld", dp[i]);

	}

	printf("\n");

		

}

int main(int argc, char *argv[]) {

	solve();

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

vector<pair<int,int> >v;

int ans[N],a[N];

int main()

{

    int n,m,i;

    cin>>n>>m;

    for(i=1;i<=n;i++)ans[i]=1;

    for(i=0;i<m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        v.push_back(make_pair(x,y));

    }

    sort(v.begin(),v.end());

    memset(a,0,sizeof a);

    for(auto x:v)

    {

        int y=x.second;

        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];

        a[y]=ans[y];

    }

    cout<<ans[1];

    for(i=2;i<=n;i++)printf(" %d",ans[i]);

    cout<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8327997407725267x):
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define maxn 200005



using namespace std;



int n,m,ans[maxn][3];

struct node

{

    int x,y;

    bool operator <(const node &a)const

    {

        return x<a.x;

    }

}d[maxn/2];



int main()

{



    scanf("%d%d",&n,&m);

    for (int i=0;i<m;i++) scanf("%d%d",&d[i].x,&d[i].y);

    sort(d,d+m);

    for (int i=1;i<=n;i++) ans[i][1]=1;

    for (int i=0;i<m;i++)

    {

      

        int p=d[i].y,t1=ans[p][1],t2=ans[p+1][1];

        ans[p][1]+=t2-ans[p][2];

        ans[p+1][1]+=t1-ans[p+1][0];



        ans[p][2]=ans[p+1][1];

        ans[p+1][0]=ans[p][1];

    }

    for (int i=1;i<n;i++) printf("%d ",ans[i][1]);

    printf("%d\n",ans[n][1]);

    return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct robot

{

	int x,y; 

}r[200005];

int left1[200005];

int right1[200005];

int res[200005];

int cmp(struct robot a,struct robot b)

{

	return a.x<b.x;

}

int main(void)

{

	int n;

	int m;

	while(~scanf("%d %d",&n,&m))

	{

		for(int i=0;i<=n;i++)

		{

			left1[i]=right1[i]=i;

		}

		memset(res,0,sizeof(res));

		for(int i=1;i<=m;i++)

		{

			scanf("%d %d",&r[i].x,&r[i].y);

		}

		sort(r+1,r+m+1,cmp);

		for(int i=1;i<=m;i++)

		{

			int xx=r[i].y;

			left1[xx]=left1[xx+1]=min(left1[xx],left1[xx+1]);

			right1[xx]=right1[xx+1]=max(right1[xx],right1[xx+1]);

		}

		cout<<right1[1]-left1[1]+1;

		for(int i=2;i<=n;i++)

		{

			cout<<" "<<right1[i]-left1[i]+1;

		}

		cout<<endl;

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.910150627961044x):
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define maxn 200005



using namespace std;



int n,m,ans[maxn][3];

struct node

{

    int x,y;

    bool operator <(const node &a)const

    {

        return x<a.x;

    }

}d[maxn/2];



int main()

{



    scanf("%d%d",&n,&m);

    for (int i=0;i<m;i++) scanf("%d%d",&d[i].x,&d[i].y);

    sort(d,d+m);

    for (int i=1;i<=n;i++) ans[i][1]=1;

    for (int i=0;i<m;i++)

    {

      

        int p=d[i].y,t1=ans[p][1],t2=ans[p+1][1];

        ans[p][1]+=t2-ans[p][2];

        ans[p+1][1]+=t1-ans[p+1][0];



        ans[p][2]=ans[p+1][1];

        ans[p+1][0]=ans[p][1];

    }

    for (int i=1;i<n;i++) printf("%d ",ans[i][1]);

    printf("%d\n",ans[n][1]);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

vector<pair<int,int> >v;

int ans[N],a[N];

int main()

{

    int n,m,i;

    cin>>n>>m;

    for(i=1;i<=n;i++)ans[i]=1;

    for(i=0;i<m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        v.push_back(make_pair(x,y));

    }

    sort(v.begin(),v.end());

    memset(a,0,sizeof a);

    for(auto x:v)

    {

        int y=x.second;

        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];

        a[y]=ans[y];

    }

    cout<<ans[1];

    for(i=2;i<=n;i++)printf(" %d",ans[i]);

    cout<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8320908269998606x):
#include <bits/stdc++.h>

using namespace std;

struct node

{

    int x,y;

} a[100005];

//int ans[200005];

int l[200005],r[200005];

int main ()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=0; i<m; i++)

        scanf("%d%d",&a[i].x,&a[i].y);

    for(int i=1; i<=n; i++)

        l[i]=r[i]=i;

    sort(a,a+m,[](node xx,node yy)

    {

        return xx.x<yy.x;

    });

    for(int i=0;i<m;i++)

    {

        l[a[i].y+1]=min(l[a[i].y],l[a[i].y+1]);

        r[a[i].y]=max(r[a[i].y],r[a[i].y+1]);

    }

    printf("%d",r[1]-l[1]+1);

    for(int i=2;i<=n;i++)

        printf(" %d",r[i]-l[i]+1);

    puts("");

}
// Slower C++ solution:
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct robot

{

	int x,y; 

}r[200005];

int left1[200005];

int right1[200005];

int res[200005];

int cmp(struct robot a,struct robot b)

{

	return a.x<b.x;

}

int main(void)

{

	int n;

	int m;

	while(~scanf("%d %d",&n,&m))

	{

		for(int i=0;i<=n;i++)

		{

			left1[i]=right1[i]=i;

		}

		memset(res,0,sizeof(res));

		for(int i=1;i<=m;i++)

		{

			scanf("%d %d",&r[i].x,&r[i].y);

		}

		sort(r+1,r+m+1,cmp);

		for(int i=1;i<=m;i++)

		{

			int xx=r[i].y;

			left1[xx]=left1[xx+1]=min(left1[xx],left1[xx+1]);

			right1[xx]=right1[xx+1]=max(right1[xx],right1[xx+1]);

		}

		cout<<right1[1]-left1[1]+1;

		for(int i=2;i<=n;i++)

		{

			cout<<" "<<right1[i]-left1[i]+1;

		}

		cout<<endl;

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.909411795420912x):
#include <bits/stdc++.h>

using namespace std;

struct node

{

    int x,y;

} a[100005];

//int ans[200005];

int l[200005],r[200005];

int main ()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=0; i<m; i++)

        scanf("%d%d",&a[i].x,&a[i].y);

    for(int i=1; i<=n; i++)

        l[i]=r[i]=i;

    sort(a,a+m,[](node xx,node yy)

    {

        return xx.x<yy.x;

    });

    for(int i=0;i<m;i++)

    {

        l[a[i].y+1]=min(l[a[i].y],l[a[i].y+1]);

        r[a[i].y]=max(r[a[i].y],r[a[i].y+1]);

    }

    printf("%d",r[1]-l[1]+1);

    for(int i=2;i<=n;i++)

        printf(" %d",r[i]-l[i]+1);

    puts("");

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



int main()

{

  int N, M;

  int dp1[200000], dp2[200000];

  vector< int > line[100001];

  iota(dp1, dp1 + 200000, 0);

  iota(dp2, dp2 + 200000, 0);



  scanf("%d %d", &N, &M);

  for(int i = 0; i < M; i++) {

    int a, b;

    scanf("%d %d", &a, &b);

    line[a].push_back(b);

  }

  for(int i = 0; i < 100001; i++) {

    for(auto& j : line[i]) {

      dp2[j - 1] = dp2[j];

      dp1[j] = dp1[j - 1];

    }

  }

  for(int i = 0; i < N; i++) {

    if(i > 0) putchar(' ');

    printf("%d", dp2[i] - dp1[i] + 1);

  }

  puts("");

}

// Faster C++ solution for the same problem (measured speedup: 1.562843759735683x):
#include <bits/stdc++.h>



using namespace std;



int main()

{

  int n, m, l[200000], r[200000];

  vector< int > line[100001];



  scanf("%d %d", &n, &m);

  for(int i = 0; i < n; i++) l[i] = r[i] = i;

  while(m--) {

    int x, y;

    scanf("%d %d", &x, &y);

    line[x].push_back(y);

  }

  for(int i = 0; i < 100000; i++) {

    for(auto &p : line[i]) {

      l[p] = l[p - 1];

      r[p - 1] = r[p];

    }

  }

  for(int i = 0; i < n; i++) {

    if(i > 0) putchar(' ');

    printf("%d", r[i] - l[i] + 1);

  }

  putchar('\n');

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define maxn 109

#define maxm 1009

using namespace std;

struct Edge

{

	int v,w,next;

}edge[maxm];

int n,m,tot,head[maxn];

int d[maxn][maxm],inq[maxn][maxm];

inline void addedge(int u,int v,int w)

{

	edge[tot].v=v;

	edge[tot].w=w;

	edge[tot].next=head[u];

	head[u]=tot++;

}

queue<pair<int,int> >Q;

void spfa()

{

	memset(d,0x3f,sizeof(d));

	d[1][0]=0;

	Q.push(make_pair(1,0));

	pair<int,int>tmp;

	while(!Q.empty())

	{

		tmp=Q.front();

		Q.pop();

		int x=tmp.first;

		int y=tmp.second;

		inq[x][y]=0;

		for(int e=head[x];e!=-1;e=edge[e].next)

		{

			int v=edge[e].v;

			if(y<m&&d[v][y+1]>d[x][y])

			{

				d[v][y+1]=d[x][y];

				if(!inq[v][y+1])

				{

					inq[v][y+1]=1;

					Q.push(make_pair(v,y+1));

				}

			}

			if(d[v][y]>d[x][y]+edge[e].w)

			{

				d[v][y]=d[x][y]+edge[e].w;

				if(!inq[v][y])

				{

					inq[v][y]=1;

					Q.push(make_pair(v,y));

				}

			}

		}

	}

}

int main()

{

	int u,v,w,c;

	while(scanf("%d%d%d",&n,&m,&c),n+m+c)

	{

		memset(head,-1,sizeof(head));

		tot=0;

		for(int i=1;i<=m;i++)

		{

			scanf("%d%d%d",&u,&v,&w);

			addedge(u,v,w);

		}

		spfa();

		int ans=m;

		for(int i=0;i<=m;i++)

		{

			if(d[n][i]<=c)

			{

				ans=i;

				break;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4997483926721846x):
#include<cstdio>

#include<vector>

#include<iostream>

#include<map>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cmath>

#define eps 1e-10

#define inf 100000000

using namespace std;

int n,m,c;

struct node

{

    int t,cost;

    node(int t=0,int cost=0):t(t),cost(cost) {}

};

vector<node> G[105];

int d[105][105];

void spfa()

{

    queue<pair<int,int> > q;

    bool vis[105][105];

    for(int i=1;i<=n;i++)

    for(int j=0;j<=n;j++) d[i][j]=inf;

    d[1][0]=0;memset(vis,0,sizeof(vis));

    q.push(make_pair(1,0));

    while(!q.empty())

    {

        pair<int,int> p=q.front();q.pop();

        int x=p.first,y=p.second;

        vis[x][y]=0;

        for(int i=0;i<G[x].size();i++)

        {

            int v=G[x][i].t,co=G[x][i].cost;

            if(d[v][y]>d[x][y]+co)

            {

                d[v][y]=d[x][y]+co;

                if(!vis[v][y])

                {

                    vis[v][y]=1;

                    q.push(make_pair(v,y));

                }

            }

            if(y<n&&d[v][y+1]>d[x][y])

            {

                d[v][y+1]=d[x][y];

                if(!vis[v][y+1])

                {

                    vis[v][y+1]=1;

                    q.push(make_pair(v,y+1));

                }

            }

        }



    }

}

main()

{

    while(scanf("%d%d%d",&n,&m,&c),n+m+c)

    {

        memset(G,0,sizeof(G));

        for(int i=1;i<=m;i++)

        {

            int s,t,c;

            scanf("%d%d%d",&s,&t,&c);

            G[s].push_back(node(t,c));

        }

        spfa();

        int ans;

        for(int j=1;j<=n;j++)

        if(d[n][j]<=c) {ans=j;break;}

        cout<<ans<<endl;

    }

}