#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt=0,head[1000005];
int n,m;
int ans[1000005],sum[1000005];
bool vis[1000005];
struct node{int to,next;}e[1000005];
void add_(int x,int y)
{
	e[++cnt].to=y;
	e[cnt].next=head[x];
	head[x]=cnt;
}
struct edge
{
	int dis;
	int pos;
	bool operator < (const edge &x) const{return x.dis<dis;}
};
priority_queue<edge>q;
void dj()
{
	q.push((edge){0,1});
	while(!q.empty())
	{
		edge t=q.top();
		q.pop();
		int x=t.pos;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(ans[y]>ans[x]+1)
			{
				sum[y]=sum[x];
				ans[y]=ans[x]+1;
				if(!vis[y])
					q.push((edge){ans[y],y});
			}
			else if(ans[y]==ans[x]+1)
			{
				sum[y]+=sum[x];
				sum[y]%=100003;
			}
		}
	}
}
signed main()
{
//	freopen("P1144_1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=2;i<=n;i++)ans[i] = 0x7ffffffffffffff;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		add_(x,y);
	}
	sum[1]=1;
	dj();
	for( int i = 1; i <= n; i++ )
		cout<<sum[i]<<endl;
	return 0;
}