/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int Mod = 100003;
int head[N] , to[N] , w[N] , ne[N] , idx;
int dis[N] , vis[N] , ans[N];
struct node
{
	int id,num;
	bool operator < (const node & a ) const {
		return num > a.num;
	}
};
inline void add(int x , int y , int z)
{
	to[++idx] = y;
	w[idx] = z;
	ne[idx] = head[x];
	head[x] = idx;
}
int n , m;
void dij()
{
	memset(dis , 0x3f , sizeof dis);
	dis[1] = 0;
	ans[1] = 1;
	vis[1] = 1;
	priority_queue< node > p;
	p.push((node){1,0});

	while(!p.empty())
	{
		node t = p.top();
		p.pop();
		if(dis[t.id] != t.num)
			continue;
		vis[t.id] = 1;
		for(int i  = head[t.id] ; i ; i = ne[i])
		{
			int u = to[i];
			if(!vis[u] && dis[u] > w[i] + dis[t.id])
			{
				dis[u] = w[i] + dis[t.id];
				ans[u] = ans[t.id] % Mod;
				p.push((node){u,dis[u]});
			}
			else if(dis[u] == w[i] + dis[t.id])
			{
				ans[u] += ans[t.id];
				ans[u] %= Mod;
			}
		}
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 0,x,y ;i < m ; i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y,1);
		add(y,x,1);
	}
	dij();
	for(int i = 1 ; i <= n ; i++)
		printf("%d\n",ans[i]%Mod);
	return 0;
}