#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e6+1;
const int M=2e6+1;
struct node{
	int value,to,next;
};
node edge[2*M];
int n,m;

int head[N],topp;
inline void add(int x,int y)
{
	edge[++topp].to=y;
	edge[topp].value=1;
	edge[topp].next=head[x];
	head[x]=topp;
	return ;
}
struct kkk{
	int point,number;
};
queue<kkk>jay;
int dis[N];//鏈€鐭綅绉绘鏁?
ll road[N];//璺緞鏉℃暟
inline void dij()
{
	jay.push((kkk){1,0});//缁撶偣 璺緞鏉℃暟 鏈€鐭綅绉绘鏁?
	road[1]++;
	while(jay.empty()==false)
	{
		kkk qaq=jay.front();
		jay.pop();
		for(int i=head[qaq.point];i;i=edge[i].next)
		{
			bool flag=false;
			if(dis[edge[i].to]==0&&edge[i].to!=1)
			{
			    dis[edge[i].to]=qaq.number+1;	
			    flag=true;
			}
			if(dis[edge[i].to]==qaq.number+1)
			    {
			      road[edge[i].to]+=road[qaq.point]*edge[i].value;	
				}
			else continue;
		    if(flag==true)
		jay.push((kkk){edge[i].to,qaq.number+1});	
		}
	}
	return ;
}
inline int read1()
{
	int res=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return res*w;
}
int main()
{
	freopen("a.in","r",stdin); 
	n=read1(),m=read1();
	
	for(int i=1;i<=m;++i)
	{
		int a,b;
		a=read1();
		b=read1();
		//if(a==b)road[a]++;
			add(a,b);
			add(b,a);
	}
	dij();
	for(int i=1;i<=n;++i)
		printf("%lld\n",road[i]%100003);
	return 0;
}
                         ```