#include<bits/stdc++.h>
using namespace std;
long long n,m,dis[4000001],v[4000001];
struct st{
	long long id,w;
	bool operator()(st s1,st s2){
		return s1.w>s2.w;
	}
};
vector<st> a[4000001];
void disa(int star){
	memset(dis,0x3f,sizeof dis);
	memset(v,0,sizeof v);
	priority_queue<st,vector<st>,st> q;
	q.push({star,0});
	while(q.size()){
		int k=0;
		st nd=q.top();
		q.pop();
		if(v[nd.id]==1) continue;
		v[nd.id]=1;
		dis[nd.id]=nd.w;
		for(auto j:a[nd.id]){
			if(!v[j.id]) q.push({j.id,j.w+nd.w});
		}
	}
}
long long f[400010]={0,1};
long long get(int x){
	if(f[x]) return f[x];
	long long tot=0;
	for(auto i:a[x]){
		if(dis[i.id]+1==dis[x]){
			tot+=get(i.id);
		}
	}
	return f[x]=tot%100003;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		a[u].push_back({v,1});
		a[v].push_back({u,1});
		
	}
	disa(1);
	for(int i=1;i<=n;i++){
		printf("%d\n",get(i));
	}
	return 0;
}