一张地图中标注了 N 个城市，城市编号为 1∼N ，城市之间通过双向的高速公路连接，假设走任意一条高速公路需要支付的费用都是相等的。

请问：从编号为 1 的城市出发，走到每个城市，如果期望支付最少的费用，请问有多少种不同的走法？

第 1 行输入整数 N 和 M ，表示有 N 个城市， M 条双向的高速公路。

接下来 M 行，每行 2 个整数 x,y，代表从 x 到 y 之间有一条高速公路。

数据范围

1 \le N \le 100000,0 \le M \le 200000。

输出 N 行，第 i 行代表，从 1 号城市到 i 号城市，支付最少路费的不同走法的数量，请输出结果数 \% 100003 的值。

如果无法走到 i 号点，请输出 0 。

样例解释

从城市 1 走到城市 5 ，最少需要经过 3 条高速公路，这样的不同走法有 4 种，分别是：1→2→4→5（2种走法，因为4→5有2条路） 和 1→3→4→5（2种走法，因为4→5有2条路）。

图论优先队列