#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int>a[1000005];
queue<int>q;
int num[1000005], dis[1000005];
bool b[1000005];

void bfs() {
	for (int i = 1; i <= n; i++)
		dis[i] = INT_MAX / 2;
	//memset(dis, INT_MAX / 2, sizeof(dis));
	q.push(1);
	b[1] = true;
	num[1] = 1;
	dis[1] = 0;
	while (!q.empty()) {
		b[q.front()] = false;
		int l = a[q.front()].size();
		for (int i = 0; i < l; i++) {
			//cout << a[q.front()][i] << '\n';
			if (dis[a[q.front()][i]] > dis[q.front()] + 1) {
				dis[a[q.front()][i]] = dis[q.front()] + 1;
				num[a[q.front()][i]] = num[q.front()] ;
				//cout << a[q.front()][i] << '-' << q.front() << '\n';
				if (!b[a[q.front()][i]]) {
					q.push(a[q.front()][i]);
					b[a[q.front()][i]] = true;
					//cout << a[q.front()][i] << '-' << q.front() << '\n';
				}
			} else if (dis[a[q.front()][i]] == dis[q.front()] + 1) {
				num[a[q.front()][i]] += dis[q.front()];
				num[a[q.front()][i]] %= 100003;
			}
		}
		q.pop();
	}
}

int main() {
	cin >> n >> m;
	while (m--) {
		int x, y;
		cin >> x >> y;
//		if (x == y)
//			continue;
		a[x].push_back(y);
		a[y].push_back(x);
	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 0; j < a[i].size(); j++)
//			cout << a[i][j] << ' ';
//		puts("");
//	}
	bfs();
	for (int i = 1; i <= n; i++)
		cout << num[i] << '\n';
	return 0;
}