WA on #1~5

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 100003

using namespace std;

const int xx = 1e6+5;

int n,m,cnt,head[xx],dis[xx],vis[xx];
long long ans[xx];

struct edge{
	int u,v,nx;
}e[4000005];

inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<='9'&&ch>='0'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

void add(int u,int v){
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].nx=head[u];
	head[u]=cnt;
}

void spfa(){
	for(int i=1;i<=n;++i) dis[i]=INF;
	queue<int> q;
	dis[1]=0;
	ans[1]=1;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nx){
			int v=e[i].v;
			if(dis[u]+1==dis[v]){
				ans[v]+=ans[u];
				ans[v]%=MOD;
			}
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				ans[v]=ans[u];
				if(!vis[v]){
					q.push(v);
					vis[v]=1;	
				}
			}
		}
	}
}

int main(){
//	freopen("P1144_1.in","r",stdin);
//	freopen("ans","w",stdout);
	n=read(),m=read();
	while(m--){
		int u=read(),v=read();
		add(u,v);
		add(v,u);	
	}
	spfa();
	for(int i=1;i<=n;++i)
		cout<<ans[i]%MOD<<"\n";
	return 0;	
}