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

int n, m,tot=0;
struct node {
	int to, next, val;
}G[1000006];
int h[1000006];
bool vis[1000006];
int dis[1000006];
int f[1000006];
struct Node {
	int x, v;
	bool operator <(const Node& a)const {
		return v > a.x;
	}
};
priority_queue<Node>s;
void add(int u, int v, int w) {
	G[++tot].to = v;
	G[tot].val = w;
	G[tot].next = h[u];
	h[u] = tot;
}
int mod = 100003;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		add(a, b, 1);
		add(b, a, 1);
	}
	for (int i = 1; i <= n; i++) {
		dis[i] = 0x3f3f3f3f;
		f[i] = 0;
	}
	s.push({1,0});
	dis[1] = 0;
	f[1] = 1;
	while (!s.empty()) {
		int x = s.top().x;
		s.pop();
		if (vis[x])continue;
		vis[x] = 1;
		for (int i = h[x]; i != 0; i = G[i].next) {
			if (dis[G[i].to] > dis[x] + G[i].val) {
				dis[G[i].to] = (dis[x] + G[i].val);
				s.push({ G[i].to,dis[G[i].to]});
				f[G[i].to] = 0;
			}
			if (dis[G[i].to] == dis[x] + G[i].val) {
				f[G[i].to] += f[x];
				f[G[i].to] %= mod;
			}
			
		}
	}
	for (int i = 1; i <= n; i++) {
		if (f[i] != 0) {
			cout << f[i]%mod << endl;
		}
		else
			cout << 0 << endl;
	}
	

	return 0;
}