#include<iostream>
#include<queue>
#define ll long long
using namespace std;
int mod=100003;
ll maxn=1e10;
ll n,m,j,i,a,b,tot=1,head[100005],d[100005],vis[100005],sum[100005];
struct node{
	ll to,nxt;
}e[200005];
void add(ll u,ll v){
	e[tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot++;
}
void SPFA()
{
	queue<ll>s;
	s.push(1);
	d[1]=0;
	vis[1]=1;
	sum[1]=1;
	while(!s.empty()){
		ll x=s.front();
		s.pop();
		for(ll k=head[x];k!=-1;k=e[k].nxt){
			ll tmp=e[k].to;
			if(!vis[tmp]){
				vis[tmp]=1;
				s.push(tmp);
				d[tmp]=d[x]+1;
				sum[tmp]=sum[x];
			}
			else
				if(d[tmp]==d[x]+1){
					sum[tmp]+=sum[x];
					sum[tmp]%=mod;
				}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(i=1;i<=n;i++)
	    head[i]=-1;
	for(i=1;i<=m;i++){
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	for(i=1;i<=n;i++)d[i]=maxn;
	SPFA();
	for(i=1;i<=n;i++)
	    cout<<sum[i]<<endl;
}

记录记录