#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int modd = 100003;
const int N = 1000005;
int n, m;
int dis[N];
int d[N];//路径总数 
vector<int> G[N]; 
bool vis[N];
void dij(){
	queue<int> q;
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	d[1] = 1;
	vis[1] = 1;
	dis[1] = 0;
	q.push(1);
	while(!q.empty()){
		int p = q.front();
		q.pop();
		for(int i = 0; i < G[p].size(); i++){
			int p2 = G[p][i];
			if(dis[p2] > dis[p]+1){
				dis[p2] = dis[p]+1;
				d[p2] = d[p];//记录路径 
				if(!vis[p2])
					vis[p2] = 1, q.push(p2);
			}
			if(dis[p2] == dis[p] + 1)
				d[p2] = (d[p2] + d[p]) % modd;
		}
	}
	return ;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dij(); 
	for(int i = 1; i <= n; i++)
		printf("%d\n", d[i]);
	return 0;
}