#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e6 + 5;
const int MOD = 1e5 + 3;

struct Edge {
    int v, w;
};

struct Point {
    int p, w;
};

struct cmp {
    bool operator()(Point &a, Point &b) {
        return a.w > b.w;
    }
};

priority_queue <Point, vector<Point>, cmp> q;
vector <Edge> e[N];
int n, m, ans[N], dis[N];
bool vis[N];

void add (int u, int v, int w) {
    e[u].push_back((Edge){v, w});
}

void Dijkstra (int n, int s) {
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    q.push((Point){s, 0});
    dis[s] = 0;
    ans[s] = 1;
    while (!q.empty()) {
        Point head = q.top();
        q.pop();
        if (vis[head.p]) {
            continue;
        }
        int now = head.p;
        vis[now] = true;
        for (int i = 0; i < (int)e[now].size(); i++) {
            int v = e[now][i].v;
            int w = e[now][i].w;
            if (dis[v] > dis[now] + w) {
                dis[v] = dis[now] + w;
                ans[v] = ans[now] % MOD;
                q.push((Point){v, dis[v]});
            } else if (dis[v] == dis[now] + w) {
                ans[v] = (ans[v] + ans[now]) % MOD;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v, 1);
    }
    Dijkstra(n, 1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}