#include<bits/stdc++.h>
#define M 20000005
using namespace std;
int D,P,C,F,S;
int qnext[M],ver[M],head[M],num,n,m;
int dis[M],tance[M],ans[M];
priority_queue<pair<int ,int> >q;
void add(int fr,int to,double di)
{
	dis[++num]=di;
	ver[num]=to;
	qnext[num]=head[fr];
	head[fr]=num;
}
void SB(){
	memset(tance,0x7f,sizeof(tance));
	tance[1]=0;
    ans[1]=1;
    q.push(make_pair(0,1));
    while (!q.empty( ) ){
        int x = q.top( ).second;
        q.pop( ) ;
        for ( int i = head[x] ; i ; i = qnext[i] ){
            int y = ver[i] , z = dis[i] ;
            if ( tance[y] > tance[x] + z ){
                tance[y] = tance[x] + z ;
                q.push(make_pair(-tance[y],y));
                ans[y]=ans[x];
            }
            else if(tance[y]==tance[x]+z)
			{
            	ans[y]=ans[x]+ans[y];
            	ans[y]%=100003;
			}
        }
    }
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y,1);
		add(y,x,1);
	}
	SB();
	for(int i=1;i<=n;i++)
	{
		if(ans[i]==0x7f)
		printf("0\n");
		else
		printf("%d  \n",ans[i]);
	}
	
	return 0;
}