rt

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

int n,m;
int u,v;
int num[1000050];
vector<int> a[1000050];
long long dist[1000050];
bool vis[1000050];

struct pts{
	int idx;
	long long dist;
	bool operator <(const pts& x)const{
		return dist>x.dist;
	}
};

void dijk(int x){
	memset(dist,0x3f,sizeof(dist));
	dist[x]=0;
	priority_queue<pts> q;
	q.push({x,0});
	pts t;
	while(q.size()){
		t=q.top();
		q.pop();
		u=t.idx;
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(int i=0;i<a[u].size();i++){
			v=a[u][i];
			if(dist[v]==dist[u]+1){
				num[v]++;
				num[v]%=100003;
			}
			if(dist[v]>dist[u]+1){
				dist[v]=dist[u]+1;
				num[v]=1;
				q.push({v,dist[v]});
			}
		}
	}
	return;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		if(u==v){
			continue;
		}
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dijk(1);
	for(int i=1;i<=n;i++){
		cout<<num[i]<<'\n';
	}
	return 0;
}