#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int n,m,d[1000005],cnt=1;
bool vis[1000005];
int ans[1000005];
const int mod=100003;
struct node
{
	int i,w;
};
vector<int>v[1000005];
priority_queue<node,vector<node>,greater<node>>pq;
bool operator>(node n1,node n2)
{
	return n1.w>n2.w;
}
int main()
{
//	freopen("P1144_4.in","r",stdin);
//	freopen("test.out","w",stdout);
	memset(d,0x7f,sizeof(d));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	ans[1]=1;
	d[1]=0;
	pq.push({1,0});
	while(cnt<=n)
	{
		node a=pq.top();
		pq.pop();
		if(vis[a.i])continue;
		vis[a.i]=true;
		for(int i=0;i<(int)(v[a.i].size());i++)
		{
			if(d[v[a.i][i]]>d[a.i]+1)
			{
				d[v[a.i][i]]=d[a.i]+1;
				pq.push({v[a.i][i],d[v[a.i][i]]});
				ans[v[a.i][i]]=ans[a.i];
			}
			else if(d[v[a.i][i]]==d[a.i]+1)
			{
				ans[v[a.i][i]]+=ans[a.i];
				ans[v[a.i][i]]%=mod;
			}
		}
		cnt++;
	}
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}

提交记录