#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
#define mo 100003
using namespace std;
const ll M=1e6+10;
ll n,m,s,cnt,dis[M],vis[M],head[M],num[M];
struct node 
{
	int d,x;
	bool operator < (const node& a) const 
	{
		return a.d<d;
	}
};
priority_queue<node>q;
struct edge 
{
	ll to,from,v;
} e[M*4];
void insert(ll x,ll y,ll z) 
{
	e[++cnt].to=y;
	e[cnt].from=head[x];
	head[x]=cnt;
	e[cnt].v=z;
	e[++cnt].to=x;
	e[cnt].from=head[y];
	head[y]=cnt;
	e[cnt].v=z;
}
void dij(ll x) 
{
	memset(dis,127,sizeof(dis));
	memset(vis,0,sizeof(vis));
	while (!q.empty()) 
	{
		q.pop();
	}
	q.push(node {0,x});
	dis[x]=0;
	vis[x]=1;
	num[x]=1;
	while (!q.empty()) 
	{
		ll u=q.top().x;
		q.pop();
		for (ll i=head[u]; i; i=e[i].from)
		{
			if (dis[e[i].to]>dis[u]+e[i].v) 
			{
				dis[e[i].to]=dis[u]+e[i].v;
				num[e[i].to]=num[u];
				if (!vis[e[i].to])	
				{
					vis[e[i].to]=1;
					q.push(node{dis[e[i].to],e[i].to});
				}
			} 
			else 
			{
				if (dis[e[i].to]==dis[u]+e[i].v)
				{
					num[e[i].to]=(num[e[i].to]+num[u])%mo;
				}
			}
			vis[u]=0;
		}
	}
	for (ll i=1; i<=n; i++) cout<<num[i]<<endl;
}
int main() {
	scanf("%lld%lld",&n,&m);
	for (ll i=1,x,y,z; i<=m; i++) 
	{
		cin>>x>>y;
		insert(x,y,1);
	}
	dij(1);
}