#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=2e6+5;
int n,m,dis[N],fr[N],tot,cnt[N];
bool vis[N];
struct E{
    int v,nt;
}e[M*2];
struct S{
    int u,k;
};
struct cmp{
    bool operator()(S &a,S &b){
        return a.k>b.k;
    }
};
priority_queue<S,vector<S>,cmp> q;
void add(int u,int v){
    tot++;
    e[tot].v=v,e[tot].nt=fr[u];
    fr[u]=tot;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push({1,0});
    cnt[1]=1;
    while(q.size()){
        S tmp=q.top();
        q.pop();
        int u=tmp.u,k=tmp.k;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=fr[u];i;i=e[i].nt){
            int v=e[i].v;
            if(dis[v]>k+1){
                dis[v]=k+1;
                cnt[v]=0;
                q.push({v,dis[v]});
            }if(dis[v]==k+1){
                cnt[v]=(cnt[v]+cnt[u])%100003;
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<cnt[i]<<endl;
}