#include<bits/stdc++.h>

#define N 1000000

#define MOD 100003

using namespace std;

int head[N],net[N],to[N];;

int a[N],d[N],cnt[N];

int n,m,cut;

priority_queue<pair<int ,int > > dl;

void add(int from,int t){net[++cut]=head[from];to[cut]=t;head[from]=cut;}

void dij(int x)

{

    memset(d,0x3f3f3f3f,sizeof d);

    dl.push(make_pair(0,x));

    a[x]=1,d[x]=0,cnt[x]=1;

    while(dl.size())

    {

        x=dl.top().second;dl.pop();

        for(int i=head[x];i;i=net[i])

        {

            int y=to[i];

            if(d[y]==d[x]+1){cnt[y]+=cnt[x];cnt[y]%=MOD;}

            if(d[y]>d[x]+1){d[y]=d[x]+1;cnt[y]=cnt[x];dl.push(make_pair(-d[y],y));}

        }

    }

}

int main()

{

    cin>>n>>m;

    for(int i=1;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    dij(1);

    for(int i=1;i<=n;i++)

        printf("%d\n",cnt[i]);

    return 0;

}