#include<bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 5, mod = 100003;
priority_queue<pii, vector<pii>, greater<pii> > q;
int n, m, c[N], d[N], x, y;
bool f[N];
vector<int> a[N];
void dj(int x)
{
	int len, s;
	memset(d, 0, sizeof(d));
	c[x] = 1;
	d[x] = 0;
	q.push({0, x});
	while(!q.empty())
	{
		len = q.top().first;
		x = q.top().second;
		q.pop();
		if(d[x] < len) 
		{
			continue;
		}
		for(int y : a[x])
		{
			if(d[y] > d[x] + 1)
			{
				c[y] = c[x] % mod;
				d[y] = d[x] + 1;
				q.push({d[y], y});
			}
			else if (d[y] == d[x] + 1)
			{
				c[y] += c[x];
				c[y] %= mod;
			}
		}
	}
}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		if(x != y)
		{
			a[x].push_back(y);
			a[y].push_back(x);
		}
	}
	dj(1);
	for(int i = 1; i <= n; i++)
	{
		cout << c[i] % mod << endl;
	}
	return 0;
}