#include<bits/stdc++.h>
//#define int long long
#define pli pair<int,long long>
using namespace std;
int n,m,s;
int _u,_v;
vector<int>e[500005];
int dist[500005];
int vis[500005];
int num[500005];
void dijkstra(){
	priority_queue<pli,vector<pli>,greater<pli> > q;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x]==1)continue;
		vis[x]=1;
		//cout<<x<<"!"<<endl;
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i];
			//cout<<x<<"  "<<y<<" "<<dist[y]<<" "<<dist[x]<<" "<<endl;
			if(dist[y]>dist[x]+1){
				dist[y]=dist[x]+1;
				q.push(make_pair(dist[y],y));
				num[y]=num[x];
			}else if(dist[y]==dist[x]+1){
				num[y]=(num[x]+num[y])%100003;
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>_u>>_v;
		e[_u].push_back(_v);
		e[_v].push_back(_u);
	}
	for(int i=1;i<=n;i++)dist[i]=1e18;
	dist[1]=0;
	num[1]=1;
	dijkstra();
	//for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
	for(int i=1;i<=n;i++){
		if(dist[i]>1e10)cout<<"0 ";
		else cout<<num[i]<<"\n";
	}
}