#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int maxn=;

const int maxm=;

const int mod=;

int n,m;

int head[maxn],cnt;

struct node{

    int v,nxt;

}e[maxn*];

void add(int u,int v){

    e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;

}

queue<int>q;

int d[maxn],v[maxn],c[maxn];

void spfa(){

    d[]=;v[]=;q.push();

    c[]=;//初值

    while(!q.empty()){

        int x=q.front();q.pop();v[x]=;

        for(int i=head[x];i;i=e[i].nxt){

            int y=e[i].v;

            if(d[y]>d[x]+){

                d[y]=d[x]+;

                c[y]=c[x];//覆蓋

                if(!v[y])q.push(y),v[y]=;

            }

            else if(d[y]==d[x]+)c[y]+=c[x],c[y]%=mod;//相等就合併

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x,y;i<=m;i++){

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

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

    }

    memset(d,0x3f,sizeof(d));

    spfa();

    for(int i=;i<=n;i++)printf("%d\n",c[i]);

}