#include <iostream>
#include <algorithm>
#include <cstring>
#define mod 100003

using namespace std;

const int N = 2000005;

int n, m, h[N], nx[N], cnt1, e[N], cnt[N], dist[N];

void add(int u, int v) {
  e[++cnt1] = v, nx[cnt1] = h[u], h[u] = cnt1;
}

bool st[N];

void spfa() {
  memset(dist, 0, sizeof dist);
  dist[1] = 0;
  int hh = 1, t = 0, q[N];
  q[++t] = cnt[1] = 1;
  st[1] = 1;
  while(hh <= t) {
    int x = q[hh++];
    for (int i = h[x]; i; i = nx[i]) {
      int y = e[i];
      if(!st[y]) {
        st[y] = 1, dist[y] = dist[x] + 1, q[++t] = y;
      }
      if(dist[y] == dist[x] + 1) {
        cnt[y] = (cnt[x] + cnt[y]) % mod;
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v; cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  spfa();
  for (int i = 1; i <= n; i++) {
    cout << cnt[i] << '\n';
  }
  return 0;
}