#include <bits/stdc++.h>
using namespace std;
struct Node {
    int u,l,x;
};
const int N = 1000010;
const int mod = 100003;
int n,m,u,v,dis[N],ans[N];
map<int, int> to[N];
queue<Node> ljj;
void ljj_push(Node u)
{
    if (dis[u.u] == 0) dis[u.u] = u.l,ans[u.u] = u.x,ljj.push(u);
    else if (u.l == dis[u.u]) (ans[u.u] += u.x) %= mod,ljj.push(u);
}
void bfs(Node start)
{
    ljj_push(start);
    while (ljj.empty() == false)
    {
        Node u = ljj.front();
        ljj.pop();
        for (auto v : to[u.u]) ljj_push({v.first, u.l + 1, u.x * v.second % mod});
    }
}

void input()
{
    cin >> n >> m;
    while (m--)
    {
        cin >> u >> v;
        ++to[u][v];
    }
}
void solve()
{
    bfs({1, 0, 1});
}
void output()
{
    for (int u = 1; u <= n; ++u) cout << ans[u] << endl;
}
int main()
{
    input();
    solve();
    output();
    return 0;
}