#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+7;
struct node{
	int e,val;
	friend bool operator < (node x,node y){
		return x.val>y.val;
	}
};
int dis[N],n,m,cnt[N]={0};
bool b[N]={0};
vector<int>g[N];
priority_queue<node>q;
void Dijkstra(int s){
    for(int i=1;i<=n;i++)	dis[i]=1e9;
	dis[s]=0;cnt[s]=1;
	q.push((node){s,0});
	while(!q.empty()){
		int u=q.top().e;
		q.pop();
		if(b[u])	continue;
		b[u]=true;
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(dis[v]==dis[u]+1)	cnt[v]+=cnt[u];
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				cnt[v]=cnt[u];
				q.push((node){v,dis[v]});
			}
		}
	}
	return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int u,v;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
	Dijkstra(1);
    for(int i=1;i<=n;i++)    cout<<cnt[i]%100003<<'\n';
    return 0;
}