cmp``` #include<bits/stdc++.h> #define int long long using namespace std; int cnt=0,head[1000005]; int n,m; int ans[1000005],sum[1000005]; bool vis[1000005]; struct node{int to,next;}e[1000005]; void add_(int x,int y) { e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt; } struct edge { int dis; int pos; bool operator < (const edge &x) const{return x.dis<dis;} }; priority_queueq; void dj() { q.push((edge){0,1}); while(!q.empty()) { edge t=q.top(); q.pop(); int x=t.pos; if(vis[x]) continue; vis[x]=1; for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if(ans[y]>ans[x]+1) { sum[y]=sum[x]; ans[y]=ans[x]+1; if(!vis[y]) q.push((edge){ans[y],y}); } else if(ans[y]==ans[x]+1) { sum[y]+=sum[x]; sum[y]%=100003; } } } } signed main() { // freopen("P1144_1.in","r",stdin); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=2;i<=n;i++)ans[i] = 0x7ffffffffffffff; for(int i=0;i<m;i++) { int x,y; cin>>x>>y; add_(x,y); } sum[1]=1; dj(); for( int i = 1; i <= n; i++ ) cout<<sum[i]<<endl; return 0; }