#include<bits/stdc++.h>
using namespace std;

const int mod = 2e6 + 3; 

struct edge {
  int to, next;
}e[5000010];

struct node {
  int dis, u;
  bool operator>(const node& a) const { return dis > a.dis; }
};

int head[1000010], dis[2000010], cnt, ans[1000010];
bool vis[1000010];
int n, m;

void add( int u, int v){
    cnt++;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

priority_queue<node, vector<node>, greater<node> > q;

void dijkstra() {
    dis[1] = 0; ans[1] = 1;
    q.push({0, 1});
    while (!q.empty()) {
        int u = q.top().u; q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i = e[i].next){
            int v = e[i].to;
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                ans[v] = ans[u];
                q.push({dis[v], v});
            } 
            else if(dis[v] == dis[u] + 1){
				ans[v] += ans[u];
				ans[v] %= mod;
			}
        }
    }
}

int main(){
	cin >> n >> m;
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	while(m --){
        int u, v;
        cin >> u >> v;
        add(u, v); add(v, u);
    }
	dijkstra();
	for(int i = 1;i <= n;i ++) cout << ans[i] << endl;
	return 0;
}