Wonderful Answer on Subtask#1

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,tot=0,s;
int d[4000010],v[4000010],hea[4000010],ans[4000010];
priority_queue<pair<int,int>>q;
struct Edge{
	int next, to, dis;
}edge[4000010];
void add(int x,int y,int z){
	edge[++tot].next=hea[x];
	edge[tot].to=y;
	edge[tot].dis=z;
	hea[x]=tot;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>x>>y;
		add(x,y,1);
		add(y,x,1);
	}
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	d[1]=0;
	ans[1]=1;
	q.push(make_pair(0,1));
	while (!q.empty()){
		int x=q.top().second;
		q.pop();
		if (v[x])continue;
		v[x]=1;
		for (int i=hea[x];i;i=edge[i].next){
			int y=edge[i].to;
			if (d[y]>d[x]+edge[i].dis) {
				d[y]=d[x]+edge[i].dis;
				ans[y]=ans[x];
				q.push(make_pair(-d[y], y));
			}
			else if(d[y]==d[x]+edge[i].dis){
				ans[y]+=ans[x];
				if(ans[y]>100003)ans[y]-=100003;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}