#include<bits/stdc++.h>
using namespace std;
const int mod=1004535809;
int d=0;
struct Alfnov{
	int a[23];
}e[300005],l[300005],b[23];
Alfnov operator+(Alfnov a,Alfnov b){
	Alfnov c;
	for(int i=1;i<=d;++i)c.a[i]=(a.a[i]+b.a[i])%mod;
	return c;
}
Alfnov operator*(int a,Alfnov b){
	Alfnov c;
	for(int i=1;i<=d;++i)c.a[i]=1ll*a*b.a[i]%mod;
	return c;
}
vector<pair<int,int>>g[100005],g2[100005];
int q[100005],deg[100005],ans[100005];
int qu[300005];
int Inverse(int x){
	int ans=1,y=mod-2;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
int main(){
	srand(time(0));
	srand(rand()+20090908);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].emplace_back(make_pair(v,i));
		g2[v].emplace_back(make_pair(u,i));
		++deg[v];
		if(u==1)++d;
	}
	int head=0,tail=-1;
	q[++tail]=1;
	while(head<=tail){
		int x=q[head++];
		for(auto P:g[x]){
			int cu=P.first;
			--deg[cu];
			if(!deg[cu])q[++tail]=cu;
		}
		if(x==1){
			int m=0;
			for(auto P:g[x]){
				++m;
				int cu=P.second;
				e[cu].a[m]=1;
			}
		}else{
			int m=0,bs=0;
			for(auto P:g2[x]){
				++m;
				int cu=P.second;
				l[m]=e[cu];
			}
			for(int i=1;i<=m;++i){
				int flag=0,wz=-1;
				for(int j=1;j<=d;++j)if(l[i].a[j]){
					wz=j,flag=1;
					break;
				}
				if(!flag)continue;
				b[++bs]=l[i];
				int ny=Inverse(l[i].a[wz]);
				for(int j=i+1;j<=m;++j)if(l[j].a[wz]){
					int c=-1ll*ny*l[j].a[wz]%mod;
					for(int k=1;k<=d;++k){
						l[j].a[k]=(l[j].a[k]+1ll*l[i].a[k]*c)%mod;
					}
				}
			}
			ans[x]=bs;
			for(auto P:g[x]){
				int cu=P.second;
				for(int i=1;i<=bs;++i)
					e[cu]=e[cu]+rand()*b[i];
			}
		}
	}
	for(int i=2;i<=n;++i){
		printf("%d",ans[i]);
		putchar((' ')*(i!=n)+('\n')*(i==n));
	}
	return 0;
}