#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
struct edge{
    int v,w;
};
struct node{
    int d,x;
    bool operator < (const node &t) const{
        return d>t.d;
    };
};
vector <edge> a[200005];
int b[200005];
priority_queue <node> q;
int vis[200005];
int ans[200005];

void dij (int s)
{
    memset(b,0x3f,sizeof(b));
    b[s]=0;ans[s]=1;
    q.push({0,s});
    while(!q.empty())
    {
        node g=q.top();
        q.pop();
        int x=g.x,d=g.d;
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=0;i<a[x].size();i++)
        {
            int v=a[x][i].v;
            if(b[v]>b[x]+a[x][i].w)
            {
                ans[v] = ans[x];
                b[v] = b[x] + a[x][i].w;
                q.push({b[v],v});
            }
            else if(b[v] == b[x] + a[x][i].w) {
                ans[v] += ans[x];
                ans[v] %= 100003;
            }
        }
    }
    return;
}
int main()
{
    int n,m;
    cin>>n>>m;
    int INF; memset(&INF, 0x3f, sizeof(INF));
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back({v,1});
    }
    dij(1);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
    return 0;
}