#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,m,s=1;
const int MOD=100003;
const int MAXN=2000006;
struct edge{
	int to;
	int next;
	int dis;
}e[MAXN];

int cnt;

int head[MAXN],dis[MAXN];
int ans[MAXN];
bool vis[MAXN];

void addedge(int u,int v,int d)
{
	cnt++;
	e[cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

struct node{
	int dis;
	int pos;
	bool operator <(const node &x)const
	{
		return x.dis<dis;
	}
};

priority_queue<node> q;

void dijsktra()
{
	dis[s]=0;
	q.push({0,s});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x])
		{
			continue;
		}
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(dis[y]==dis[x]+e[i].dis)
			{
				ans[y]=(ans[x]+ans[y])%MOD;      
				if(!vis[y])
				{
					q.push({dis[y],y});	
				}	
			}
			if(dis[y]>dis[x]+e[i].dis)
			{
				
				dis[y]=dis[x]+e[i].dis;	
				ans[y]=ans[x]%MOD;
				if(!vis[y])
				{
					q.push({dis[y],y});	
				}		
			}
//			cout<<y<<" "<<ans[y]<<endl;
		}
	}
}

signed main()
{
	cin>>n>>m;
	int u,v,d;
	for(int i=1;i<=n;i++)
	{
		dis[i]=0x7fffffff;
		ans[i]=1;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		addedge(u,v,1);	
		addedge(v,u,1);
	}
//	cout<<endl;
	dijsktra();
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]%MOD<<endl;
	}
	return 0;
}