rt.AC#1,#3,#5.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=1e5+3;
const int inf=0x3f3f3f3f3f3f3f3f;
int dis[N],ans[N],n,m;
vector<pair<int,int> >G[N];
void Dijkstra(int s)
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
	Q.push(make_pair(s,0));
	for(int i=1;i<=n;i++) dis[i]=inf;
	dis[s]=0,ans[s]=1;
	while(!Q.empty())
    {
		pair<int,int>now=Q.top();Q.pop();
		int u=now.first,w=now.second;
		if(w>dis[u]) continue;
		for(pair<int,int>i:G[u])
		{
			int v=i.first;
			if(dis[u]+i.second<dis[v])
			{
				dis[v]=dis[u]+i.second;ans[v]=ans[u];
				Q.push(make_pair(v,dis[v]));
			}
			else if(dis[u]+i.second==dis[v])
				ans[v]=(ans[u]+ans[v])%mod;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;cin>>u>>v;
		G[u].push_back(make_pair(v,1));
		G[v].push_back(make_pair(u,1));
	}
	Dijkstra(1);
//	for(int i=1;i<=n;i++) cout<<dis[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++) cout<<ans[i]%mod<<endl;
	return 0;
}