#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6;
struct node{
	int to,w,next;
}e[4*MAXN];
int cnt,head[MAXN],dis[MAXN],vis[MAXN],tong[MAXN];
void add(int x,int y,int w){
	e[++cnt].to=y;
	e[cnt].w=w;
	e[cnt].next=head[x];
	head[x]=cnt;
}
priority_queue<pair<int,int> >q;
void dij(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0,tong[s]=1;
	q.push(make_pair(0,s));
	while(q.size()){
		int to=q.top().second;
		q.pop();
		if(!vis[to]){
			vis[to]=1;
			for(int i=head[to];i;i=e[i].next){
				int go=e[i].to,k=e[i].w;
				if(dis[go]>k+dis[to]){
					tong[go]=1;
					dis[go]=k+dis[to];
					q.push(make_pair(-dis[go],go)); 
				}else if(dis[go]==k+dis[to]){
					tong[go]++;
				}
			}
		}
			
	}
} 
int n,m;
signed main(){
	cin>>n>>m;
	for(int x,y;m;m--){
		cin>>x>>y;
		add(x,y,1);
		add(y,x,1);
	}
	dij(1);
	for(int i=1;i<=n;i++){
		cout<<tong[i]%100003<<"\n"; 
	}
	return 0;
}