#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e6;

struct node{
	int to,next,w;
};

struct node1{
	int pos,dist;
	bool friend operator < (node1 a,node1 b){
		return a.dist>b.dist;
	}
};

node edge[maxn];
int vex[maxn],dist[maxn],vis[maxn],v,e,ei;
int ans[maxn];

void add(int v1,int v2,int w){
	edge[++ei].to=v2;
	edge[ei].next=vex[v1];
	edge[ei].w=w;
	vex[v1]=ei;
}

void dijkstra(int s){
	for(int i=1;i<=v;i++){
		dist[i]=0x7f7f7f7f;
	}
	dist[s]=0;
	priority_queue<node1> que;
	que.push((node1){s,0});
	while(!que.empty()){
		node1 t=que.top();
		que.pop();
		if(vis[t.pos]){
			continue;
		}
		vis[t.pos]=1;
		int index=vex[t.pos];
		while(index!=-1){
			int u=edge[index].to,w=edge[index].w;
			if(dist[u]>dist[t.pos]+w){
				dist[u]=dist[t.pos]+w;
				que.push((node1){u,dist[u]});
			}else if(dist[u]==dist[t.pos]+w){
				ans[u]+=ans[t.pos];
				ans[u]%=100003;
			} 
			index=edge[index].next;
		}
	}
}

int main(){
	cin>>v>>e;
	memset(vex,-1,sizeof(vex));
	for(int i=1;i<=e;i++){
		int v1,v2;
		cin>>v1>>v2;
		add(v1,v2,1);
		add(v2,v1,1);
	} 
	dijkstra(1);
	for(int i=1;i<=v;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}