题目描述

​ 梦梦给出了一个 n 个顶点 m 条边的无向无权图，顶点编号为 $1\sim n$ 。 ​ 熊熊想知道从顶点 1 开始，到其他每个点的最短路有几条，答案对 100003 取模。 ​

输入格式

​ 一行，一个正整数 n,m 。 ​ 之后 m 行，每行给出 $u_i,v_i$。 ​

输出格式

​ 输出 n 行，每行一个整数，表示答案。 ​

样例

​

样例输入

​

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

​

样例输出

​

1
1
1
2
4

​

样例解释

​ 1 至 5 的最短路共 4 条， (1,2,4,5),(1,3,4,5) ，其中 (4,5) 边有两条。 ​

数据范围与提示

​ 对于 30% 的数据，$1 \leq n,m\leq 10^3$。 ​ 对于 100% 的数据，$1 \leq n,m \leq 10^6$ 。 ​