题目描述

一张地图中标注了 $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$ 。

样例

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

1
1
1
2
4

说明

样例解释

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