#include<bits/stdc++.h>
using namespace std;
vector<int>a[1000001];
struct Node{
	int w,js;
	bool bj;
}ans[1000001];
struct ycy{
	int now,w; 	
};
queue<ycy>q;
void read(int &x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x*=10;
		x+=ch-'0';
		ch=getchar();
	}
}
void bfs(int p,int w){
	//printf("%d %d\n",p,w);
	if(p==1){
		ans[1].js=1;
	}
	else if(w<=ans[p].w){
		ans[p].js++;
		ans[p].js%=100003;
	}
	else{
		return;
	}
	ans[p].w=w;
	ans[p].bj=1;
	for(auto it:a[p]){
		if(!ans[it].bj){
			q.push({it,w+1});
			//ans[it].bj=1;
		}
	}
}
int main(){
	int n,m;
	read(n);
	read(m);
	for(int i=1;i<=m;i++){
		int u,v;
		read(u);
		read(v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		ans[i].w=114514;
	}
	q.push({1,1});
	while(!q.empty()){
		bfs(q.front().now,q.front().w);
		q.pop();
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i].js%100003);
	}
	return 0;
}