#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
const int M = 100003;
int h[N], e[N],  ne[N], idx;
int dis[N];
bool vis[N];
int cnt[N];
typedef pair<int, int> PII;

priority_queue<PII, vector<PII>, greater<PII>> q;

int n, m, s;

void add(int a, int b, int c) {
	if (a != b)
		e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra() {
	dis[1] = 0;
	cnt[1] = 1;
	q.push({0, 1});
	while (q.size()) {
		auto t = q.top();
		q.pop();
		int ver = t.second, distance = t.first;

		if (vis[ver])
			continue;
		//cout << ver << " " << cnt[ver] << endl;
		vis[ver] = 1;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];

			if (dis[j] == dis[ver] + 1) {
				cnt[j] += cnt[ver];
				cnt[j] %= M;
				//	q.push({dis[j], j});
			}
			if (dis[j] > dis[ver] + 1) {
				dis[j] = dis[ver] + 1;
				cnt[j] += cnt[ver];
				cnt[j] %= M;
				q.push({dis[j], j});
			}
		}
	}
}

int main() {
	cin >> n >> m ;
	memset(h, -1, sizeof(h));
	memset(dis, 9998, sizeof(dis));
	for (int i = 1; i <= m; i++) {
		int ui, vi;
		cin >> ui >> vi ;
		add(ui, vi, 1);
		add(vi, ui, 1);
	}
	dijkstra();
	for (int i = 1; i <= n; i++)
		if (cnt[i] != 9998)
			cout << cnt[i] % M << endl;
		else
			cout << 0 << endl;
}