//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<queue>
//#include<vector>
//#include<cmath>
//#include<algorithm>
//using namespace std;
//const int N=1e6+5,M=2e6+5;
//const int inf=999999999,mod=1e5+3;
//int nxt[M*2],to[M*2],last[N],vis[N];
//int tot,n,m,x,y,z;
//int ans[N];
//int s[N];
//void add(int x,int y)
//{
//	tot++;
//	nxt[tot]=last[x];
//	last[x]=tot;
//	to[tot]=y;
//	return ;
//}
//void bfs()
//{
//	priority_queue<int,vector<int>,greater<int>> q;
//	q.push(1);
//	s[1]=0;
//	ans[1]=1;
//	while(!q.empty())
//	{
//		int x=q.top();
//		q.pop();
//		if(vis[x]) continue;
//		vis[x]=1;
//		for(int i=last[x];i;i=nxt[i])
//		{
//			if(s[x]+1<s[to[i]])
//			{
//				s[to[i]]=s[x]+1;
//				ans[to[i]]=0;
//			}
//			if(s[x]+1==s[to[i]])
//			{
//				ans[to[i]]=(ans[to[i]]+ans[x])%mod;
//			}
//			q.push(to[i]);
//		}
//	}
//}
//int main()
//{
//	freopen("P1144_2.in","r",stdin); 
//	scanf("%d%d",&n,&m);
//	for(int i=1;i<=n;i++) s[i]=inf;
//	for(int i=1;i<=m;i++)
//	{
//		scanf("%d%d",&x,&y);
//		add(x,y);
//		add(y,x);
//	}
//	bfs();
//	for(int i=1;i<=n;i++)
//	{
//		printf("%d\n",ans[i]%mod);
//	}
//	return 0;
//}//dijkstra 60 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e6+5,M=2e6+5;
const int inf=999999999,mod=1e5+3;
int nxt[M*2],to[M*2],last[N],vis[N];
int tot,n,m,x,y,z;
int ans[N];
int s[N];
void add(int x,int y)
{
	tot++;
	nxt[tot]=last[x];
	last[x]=tot;
	to[tot]=y;
	return ;
}
void bfs()
{
	priority_queue<int,vector<int>,greater<int>> q;
	q.push(1);
	s[1]=0;
	ans[1]=1;
	while(!q.empty())
	{
		int x=q.top();
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=last[x];i;i=nxt[i])
		{
			if(s[x]+1<s[to[i]])
			{
				s[to[i]]=s[x]+1;
				ans[to[i]]=0;
			}
			if(s[x]+1==s[to[i]])
			{
				ans[to[i]]=(ans[to[i]]+ans[x])%mod;
			}
			q.push(to[i]);
		}
	}
}
int main()
{
//	freopen("P1144_2.in","r",stdin); 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) s[i]=inf;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	bfs();
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",ans[i]%mod);
	}
	return 0;
}