#include<bits/stdc++.h>
using namespace std;
const int mod=100003;
int n,m,dis[1000001],a[1000001];
bool vis[1000001];
vector <int> e[1000001];

void add(int x,int y)
{
    e[x].push_back(y);
    e[x].push_back(x);
}
void bfs()
{
    memset(dis,0x3f3f3f3f,sizeof dis);
    queue <int> que;
    a[1] =  vis[1] = 1;
    dis[1] = 0;
    que.push(1);
    while(!que.empty())
    {
        int x=que.front();que.pop();
        for(auto v:e[x])
        {
            if(!vis[v])
            {
                vis[v] = true;
                dis[v] = dis[x]+1;
                que.push(v);
            }
            if(dis[v]==dis[x]+1)
            {
                a[v] = (a[x]%mod+a[v]%mod)%mod;
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        add(x,y);
    }
    bfs();
    for(int i=1;i<=n;i++) printf("%d\n",a[i]);
    return 0;
}