#include <bits/stdc++.h>
#define N 1000010
#define mod 100003

using namespace std;

int ans[N], head[N], n, m, tot, flag[N], dist[N];

inline int read() {
	int x = 0;
	char c = getchar();
	while (c < '0' || c>'9') c = getchar();
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x;
}

struct Edge {
    int next, w, to;
};

Edge edge[N];

void add_edge(int x, int y, int ww) {
    edge[tot].w = ww;
    edge[tot].to = y;
    edge[tot].next = head[x];
    head[x] = tot ++;
}

void dijkstra() {
    priority_queue<pair<int, int>> que;
    que.push(make_pair(0, 1));
    for (int i = 1; i <= n; i++) {
        dist[i] = 2147483647;
        flag[i] = 0;
    }
    dist[1] = 0;
    ans[1] = 1;
    while(!que.empty()) {
        int x = que.top().second;
        que.pop();
        if (flag[x]) continue;
        flag[x] = 1;
        for (int i = head[x]; i != -1; i = edge[i].next) {
            int y = edge[i].to;
            if (flag[y] == 0 && dist[y] > dist[x] + edge[i].w) {
                dist[y] = dist[x] + edge[i].w;
                ans[y] = ans[x];
                ans[y] %= mod;
                que.push(make_pair(-dist[y], y));
            }
            else if(flag[y] == 0 && dist[y] == dist[x] + edge[i].w) {
                ans[y] += ans[x];
                ans[y] %= mod;
            }
        }
    }
    return;
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        int x, y;
        x = read();
        y = read();
        add_edge(x, y, 1);
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

为什没输出呀……