#include<bits/stdc++.h>
using namespace std;
//_______________________________________________________________________________________________________________________________________________________
const int N = 1000010, MOD = 100003; 
int head[N], to[N << 1], val[N << 1], nxt[N << 1], rp;
int dis[N], vis[N], cnt[N];
void add_edge(int u, int v, int w){
	to[++rp] = v;
	val[rp] = w;
	nxt[rp] = head[u];
	head[u] = rp;
}
void dijkstra(int s){
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	memset(cnt, 0, sizeof(vis));
	dis[s] = 0, cnt[s] = 1;
	q.push(make_pair(0, s));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(!vis[x]){
			vis[x] = 1;
			for(int i = head[x]; i; i = nxt[i]){
				if(dis[to[i]] > dis[x] + val[i]){
					dis[to[i]] = dis[x] + val[i];
					cnt[to[i]] = cnt[x];
					q.push(make_pair(dis[to[i]], to[i]));
				}
				else if(dis[to[i]] == dis[x] + val[i]) cnt[to[i]] = (cnt[to[i]] + cnt[x]) % MOD;
			}
		}
	}
}
int n, m, s;
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v, 1);
		add_edge(v, u, 1);
	}
	dijkstra(1);
	for(int i = 1; i <= n; i++) printf("%d\n", cnt[i]);
	return 0;
}