#include <bits/stdc++.h>
using namespace std;

const int N=1e6+1000,mod=100003;
vector <int> e[N];
int n,m,ans[N],dist[N];
bool v[N];
struct node{
	int to,w;
	bool operator > (const node &a)const{
		return w>a.w;
	}
};
void dijkstra(int s){
	ans[s]=1;
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	priority_queue <node,vector<node>,greater<node> > p;
	p.push({s,0});
	node h;
	while(!p.empty()){
		h=p.top();
		p.pop();
		if(v[h.to])continue;
		v[h.to]=1;
		for(int i:e[h.to]){
			if(dist[i]>dist[h.to]+1){
				dist[i]=dist[h.to]+1;
				ans[i]=0;
				p.push({i,dist[i]});
			}
			if(dist[i]==dist[h.to]+1){
				ans[i]+=ans[h.to];
				ans[i]%=mod;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	int u,v;
	for(int i=1; i<=m; i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dijkstra(1);
	for(int i=1; i<=n; i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}