#include <bits/stdc++.h>
#define INF 1e9
#define int long long
#define endl '\n'
using namespace std;
const int p = 100003;

void solve()
{	
	int n,m;
	cin >> n >> m;
	vector<vector<int>> e(n+1);
	vector<int> dis(n+1,INF),dp(n+1,0);
	for(int i = 1;i<=m;i++)
	{
		int x,y;cin >> x >> y;
		// if(x==y) continue;
		e[x].push_back(y),e[y].push_back(x);
	}

	auto Dijkstra = [&]() ->void {
		vector<bool> vis(n+1);
		dis[1] = 0,dp[1] = 1;
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
		q.push({0,1});
		while(q.size())
		{
			pair<int,int> t = q.top();
			q.pop();
			int u = t.second;
			if(vis[u]) continue;
			vis[u] = 1;
			for(auto x:e[u])
			{
				if(dis[x]>dis[u]+1) 
				{
					dis[x] = (dis[u]+1)%p;
					dp[x] = dp[u]%p;
					q.push({dis[x],x});
				}
				else if(dis[x] == dis[u]+1) dp[x] = (dp[x]+dp[u])%p;
			}
		}
	};
	Dijkstra();
	dp[1] = 1;
	for(int i = 1;i<=n;i++) cout << dp[i] << endl;
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t--)
	{
		solve();
	}

	return 0;
}