#include<bits/stdc++.h> #define int long long using namespace std; vector e[2000010]; int d[2000010]; int f[2000010]; void bfs(){ queue q; q.push(1); while(!q.empty()){ int t=q.front(); q.pop(); for(auto v:e[t]){ if(d[v]>d[t]+1){ d[v]=d[t]+1; f[v]=f[t]; q.push(v); } else if(d[v]==d[t]+1){ f[v]+=f[t]; f[v]%=100003; } } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int s,v; cin>>s>>v; e[s].push_back(v); e[v].push_back(s); } memset(d,0x3f,sizeof d); d[1]=0; f[1]=1; bfs(); for(int i=1;i<=n;i++){ cout<<(f[i]%100003)<<"\n"; } return 0; }