#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5,M = 2e5+5;
int n,m;
int head[N],cnt;
struct node{
    int next,to;
}eg[M];
void add(int a,int b){
    eg[++cnt].to = b;
    eg[cnt].next = head[a];
    head[a] = cnt;
}
bool vis[N];
int dis[N],ans[N];
void dijkstra(int s){
    priority_queue<pair<int,int>> hp;
    memset(dis,0x3f,sizeof dis);
    hp.push(make_pair(0,s));
    dis[s] = 0;
    while(hp.size()){
        pair<int,int> cur = hp.top();
        hp.pop();
        int u = cur.second;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i = eg[i].next){
            int y = eg[i].to;
            if(dis[y] > dis[u]+1){
                dis[y] = dis[u]+1;
                ans[y] = ans[u];
                hp.push(make_pair(-dis[y],y));
            }
            if(dis[y] == dis[u]+1)
                ans[y] = (ans[u]+ans[y]) % 100003;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int x,y;
        cin >> x >> y;
        add(x,y);
        add(y,x);
    }
    ans[1] = 1;
    dijkstra(1);
    for(int i = 1;i <= n;i ++)
        cout << ans[i] << "\n";
    return 0;
}

输出：

1
2
2
6
18