题解

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1111111],dis[1111111],vis[1111111],mod=100003;
vector<int>g[1111111];
void gs(){
	memset(dis,0x3f,sizeof(dis));
	queue<int>q;
	q.push(1);
	dis[1]=0;
	f[1]=vis[1]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(auto v:g[u]){
			if(dis[v]>dis[u]+1)q.push(v),f[v]=f[u],dis[v]=dis[u]+1;
			else if(dis[v]==dis[u]+1)f[v]+=f[u],f[v]%=mod;
		}
	}
}
signed main() {
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	gs();
	for(int i=1;i<=n;i++)cout<<f[i]<<endl;
    return 0;
}