#include <bits/stdc++.h>

 #define Set(a, v) memset(a, v, sizeof(a))

 #define For(i, l, r) for(int i = (l); i <= (int)(r); ++i)

 #define Fordown(i, r, l) for(int i = (r); i >= (int)(l); --i)

 using namespace std;

 inline int read(){

     int x = , fh = ; char ch;

     for(; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -;

     for(; isdigit(ch); ch = getchar()) x = (x<<) + (x<<) + (ch^'');

     return x * fh;

 }

 const int N = , M =  << , inf = 0x3f3f3f3f;

 const int mod = ;

 struct graph {

     int to[M], Head[N], Next[M], val[M], e;

     void init() {

         e = ;

         Set(Head, );

     }

     void add_edge (int u, int v, int w) {

         to[++e] = v;

         val[e] = w;

         Next[e] = Head[u];

         Head[u] = e;

     }

 };

 graph G;

 #define Travel(i, u, G) for(int i = G.Head[u]; i; i = G.Next[i])

 //链式前向星的存图方式，Travel是遍历，这样便于我们写多图，而且挺方便的

 bool inq[N];

 int dis[N];

 void spfa() {

     queue<int> Q;

     Set(dis, inf);

     Q.push(); dis[] = ;

     while (!Q.empty() ) {

         int now = Q.front(); Q.pop();

         inq[now] = false;

         Travel(i, now, G) {

             int v = G.to[i];

             if (dis[v] > dis[now] + G.val[i]) {

                 dis[v] = dis[now] + G.val[i];

                 if (!inq[v]) { inq[v] = true; Q.push(v); }

             }

         }

     }

 }

 //裸的spfa不解释 

 int dp[N]; //记忆化搜索所记忆的东西（表示到这个点最短路的条数）

 int dfs(int u, int deep) { //deep存储从1到这个点的深度

     if (dp[u]) return dp[u]; //如果已经到过这个点直接返回条数

     Travel(i, u, G) {

         int v = G.to[i];

         if (deep -  == dis[v]) //如果deep-1等于之前算出来的dis（最短路径）

         //也就是说，当前我们所走的路径是可以走通的最短路之一

             dp[u] = (dp[u] + dfs(v, deep-)) % mod; //计算路径个数，并继续向下递归

             //很简单的一个加法原理

     }

     return dp[u]; //最后记得返回这个值

 }

 int main (){

     G.init();

     int n  = read(), m = read();

     while (m--) {

         int u = read(), v = read();

         G.add_edge(u, v, );

         G.add_edge(v, u, );

     }

     spfa();

     dp[] = ;

     For (i, , n)

         dp[i] = dfs(i, dis[i]);

         //我们从每一个点向起点走回去，所以一开始的深度是当前这个点的最短路

         //这样可以解释之前为什么是deep-1了

     For (i, , n)

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

         //最后输出结果

 }