#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;

const int N = 20000010;
int n, m;

int e[N], ne[N], h[N], idx;
int dist[N];
bool st[N];
int res[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while(heap.size()){
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i]){
            int b = e[i];
            if (dist[ver] + 1 < dist[b]){
                dist[b] = dist[ver] + 1;
                res[b] = res[ver];
                heap.push({dist[b], b});
            }
            else if(dist[ver] + 1 == dist[b]){
                res[b] += res[ver];
                heap.push({dist[b], b});
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    res[1] = 1;
    memset(h, -1, sizeof h);
    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    dijkstra();
    for(int i = 1; i <= n; i++){
        printf("%d\n", res[i] % 10003);
    }
    return 0;
}