#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Max 1001000
#define mod 100003
ll ans[Max];
map<pair<int,int>, ll> edge;
vector<int> e[Max];
int n, m;
ll dist[Max];
bool vis[Max];
ll mul(ll x, ll y)
{
	ll result = 0;
	while (y)
	{
		if (y & 1)
			result = (result + x) % mod;
		y >>= 1;
		x = (x + x) % mod;
	}
	return result;
}
struct bian
{
	int from;
	int to;
	ll val;
	friend bool operator <(const bian& q1, const bian& q2)
	{
		return q1.val > q2.val;
	}
};
void built()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		edge[make_pair(x, y)] = edge[make_pair(y, x)] = 1;
		e[x].push_back(y);
		e[y].push_back(x);
	}
}
void disj()
{
	priority_queue<bian, vector<bian>> q;
	q.push({ 1,1,0 });
	ans[1]=ans[0] = 1;
	edge[make_pair(1, 1)] = 1;
	while (!q.empty())
	{
		bian _top = q.top();
		q.pop();
		if (vis[_top.to])
		{
			if (dist[_top.to] == _top.val)
			{
				ans[_top.to] = (ans[_top.to] + mul(ans[_top.from] , edge[make_pair(_top.from, _top.to)])) % mod;
				//ans[_top.to] = (ans[_top.to] + (ans[_top.from] * edge[make_pair(_top.from, _top.to)]) % mod) % mod;
			}
			continue;
		}
		vis[_top.to] = 1;
		dist[_top.to] = _top.val;
		ans[_top.to] = mul(ans[_top.from] , edge[make_pair(_top.from, _top.to)]);
		for (auto son : e[_top.to])
		{
			if (!vis[son])
			{
				q.push({ _top.to,son,_top.val + 1 });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	built();
	disj();
	for (int i = 1; i <= n; i++)
	{
		cout << ans[i] << '\n';
	}
	return 0;
}