#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[1000002];
int used[1000002];
int vis[1000002];
const int MOD=100003;

struct point
{
	int x,step;
}q[10000001],s;

int front,tail;

void bfs()//广搜
{
	front=tail=1;
	memset(used,0x7f7f7f,sizeof(used));//used代表走到一个点的最短路径
	memset(vis,0,sizeof(vis));//vis代表最短路数量
	used[1]=0;
	s.x=1,s.step=0;
	q[1]=s;
	vis[1]=1;
	while(front<=tail)
	{
		point u=q[front++];
		point v;
		for(int i=0; i<g[u.x].size(); i++)
		{
			v.x=g[u.x][i],v.step=u.step+1;
			if(used[v.x]<v.step) continue;//如果不是最短路，忽略
			vis[v.x]=(vis[v.x]+1)%MOD;//增加最短路数量
			used[v.x]=v.step;//登记最短路
			q[++tail]=v;//入队
		}
	}
}

void output(){
	for(int i=1; i<=n; i++)
	{
		printf("%d\n",(vis[i]%MOD));//输出
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
        //无向图加边
	}
	bfs();
	output();
	return 0;
}