#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1000010, M = 10010;
constexpr int inf = 1E18, mod = 100003;
int n, m, dis[N], ans[N];
vector<int> G[N];
inline void BFS() {
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    q.push(1);
    dis[1] = 0;
    ans[1] = 1;
    while(q.size()) {
        int u = q.front();
        q.pop();
        for (auto v : G[u]) {
            if(dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                ans[v] = ans[u];
                q.push(v);
            }else if(dis[v] == dis[u] + 1) {
                ans[v] = (ans[v] + ans[u]) % mod;
            }
        }
    }
}
inline void Main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    BFS();
    for (int i = 1; i <= n; i ++) {
        cout << ans[i] << " \n";
    }
}
signed main() {    
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1; 
    while(T --) Main();
    return 0;
}