#4MLE，#5TLE

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,x,y;
int M[1000003]={0,1};
int sum[1000003]={0,1},i,j;
vector<int>way[1000003];
void bfs()
{
	int deep=0,T=n-1,p,s;
	queue<int>e;
	e.push(1);
	while(T>0&&!e.empty())
	{
		p=e.size();
		for(i=1;i<=p;i++)
		{
			s=e.front(),e.pop();
			if(M[s]==0)  M[s]=deep,sum[s]=(sum[s]+1)%100003,T--;
			else if(M[s]==deep)  sum[s]=(sum[s]+1)%100003;
			else if(s!=1)  continue;
			for(j=0;j<way[s].size();j++)  if(M[way[s][j]]==0)  e.push(way[s][j]);
		}
		deep++;
	}
}
int main()
{
	for(scanf("%d%d",&n,&m),i=1;i<=m;i++)
	{	
		scanf("%d%d",&x,&y);
		if(x==y)  continue;
		way[x].push_back(y),way[y].push_back(x);
	}
	for(bfs(),i=1;i<=n;i++)  printf("%d\n",sum[i]%100003);
	return 0;
}