rt.

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#define int long long
using namespace std;
const int N = 4e6 + 5, mod = 100003;
int n, m;
int cnt[N];
int d[N], vis[N], minn[N];
struct poi{
	int v, w, cnt;
};
map<pair<int, int>, int> mp;
queue<poi> q;
vector<poi> g[N];
inline void bfs()
{
	memset(minn, 0x3f, sizeof(minn));
	vis[1] = 1;
	q.push({1, 1, 1});
	while(!q.empty()){
		poi p = q.front();
		q.pop();
		for(int i = 0; i < g[p.v].size(); i++){
			int v = g[p.v][i].v, w = g[p.v][i].w;
			if((vis[v] < cnt[v] && p.cnt + 1 == minn[v]) || minn[v] == 4557430888798830399){
				q.push({v, p.w * mp[make_pair(p.v, v)], p.cnt + 1});
				vis[v]++;
				d[v] += p.w * mp[make_pair(p.v, v)] % mod;
				minn[v] = p.cnt + 1;
			}
		}
	}
}
signed main()
{
//	freopen("T2.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		if(u == v) continue;
		if(!mp[make_pair(u, v)]) g[u].push_back({v, 1, 0}), g[v].push_back({u, 1, 0});
		mp[make_pair(u, v)]++;
		cnt[v]++;
	}
	d[1] = 1;
	bfs();
	for(int i = 1; i <= n; i++) cout << d[i] << "\n";
	return 0;
}