#include<bits/stdc++.h>
using namespace std;
const long long N = 4e6+10;
const long long M = 4e6+10;
const long long MOD = 1e5+3;
long long head[N];
struct RCM {
	long long to, nxt, w;
} edge[400010];
long long cnt = 0;
long long dist[N];
long long vis[N]; //标记点是否在队列里面 
long long n, m;
long long neg[N]; //记录每个点入队的次数 
void adde(long long u, long long v, long long w) {
	cnt++;
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

long long ans[N]; 
void BFS(long long s) { //无边权，或边权为1 
	queue <long long> q;
	dist[s] = 0;
	ans[s] = 1;
	q.push(s);
	while(!q.empty()) {
		long long u = q.front();
		q.pop();
		for(long long i = head[u];i;i = edge[i].nxt) {
			long long v = edge[i].to;
			if(dist[v] == 0 || dist[v] > dist[u]+1) {
				dist[v] = (dist[u]+1) % MOD;
				ans[v] = ans[u];
				q.push(v);
			}
//			if(!vis[v]) {
//				dist[v] = dist[u]+1;
//				ans[v] = ans[u];
//				q.push(v);
//			}
			else if(dist[v] == dist[u] + 1) {
				ans[v] = (ans[v] + ans[u]) % MOD;
			}
		}
	}
} 
int main() {
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	cin>>n>>m;
	for(long long i = 1;i <= m;i++) {
		long long u,v;
		cin>>u>>v;
		if(u == v) continue;
		adde(u,v,1); //边权可以为1
		adde(v,u,1); //双向 
	}
	BFS(1);
	cout<<1<<'\n';
	for(long long i = 2;i <= n;i++) 
		cout<<ans[i]<<'\n';
}