#4蜜汁WA 求助

#include <bits/stdc++.h>
using namespace std;
int i,m,n,x,y;
int v[2000000][2],w[2000000],ans[1000000];
vector<int> u[1000000];
bool b[1000000];
void spfa(){
	queue<int> q;
	int dis[1000000];
	int t,a,p;
	b[1]=true;
	q.push(1);
	for(int j=1;j<=n;j++){
	    dis[j]=10000000;
	    ans[j]=1;
	}
	dis[1]=0;
	while(q.empty()==false){
		t=q.front();
		q.pop();
		b[t]=false;
		if(u[t].empty()==false)
		   for(unsigned int j=0;j<=u[t].size()-1;j++){
		   	   a=u[t][j];
		   	   if(v[a][1]==t) p=v[a][2];
		   	   else p=v[a][1];
		   	   if(dis[p]==dis[t]+w[a]){
		   	      ans[p]+=ans[t];
		   	      ans[p]=ans[p]%100003;
		   	   }
		   	   if(dis[p]>dis[t]+w[a]){
		   	   	  dis[p]=dis[t]+w[a];
		   	   	  ans[p]=ans[t];
		   	   	  ans[p]=ans[p]%100003;
		   	   	  if(b[p]==false){
		   	   	  	 b[p]=true;
		   	   	  	 q.push(p);
			   	  }
			   }
		   }
	}
}
int main(){
	cin>>n>>m;
	for(i=1;i<=m;i++){
		cin>>x>>y;
		u[x].push_back(i);
		u[y].push_back(i);
		w[i]=1;
		v[i][1]=x;
		v[i][2]=y;
	}
	spfa();
	ans[1]=1;
	for(i=1;i<=n;i++)
	    cout<<ans[i]<<endl;
	return 0;
}