#include<bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 1e7 + 5;
const int MOD = 100003;
int n, m, t[N], h[N], ne[N], ans[N], d[N], pos;
bool vis[N];
priority_queue<PII>que;
void add (int x, int y) {
    t[++pos] = y;
    ne[pos] = h[x];
    h[x] = pos;
}
int main () {
    cin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++) {
        d[i] = 1e9;
    }
    d[1] = 0;
    ans[1] = 1;
    que.push({0, 1});
    while (que.size()) {
        PII pi = que.top();
        que.pop();
        if (!vis[pi.second]) {
            vis[pi.second] = true;
            for (int i = h[pi.second], x; i; i = ne[i]) {
                x = t[i];
                if (d[x] > d[pi.second] + 1) {
                    d[x] = d[pi.second] + 1;
                    ans[x] = ans[pi.second];
                    que.push({-d[x], x});
                }
                else if (d[pi.second] == d[x] + 1) {
                    ans[x] = (ans[x] + ans[pi.second]) % MOD;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}