题目描述

在一张无向无权图中，$N$ 个顶点的编号是 $1$ 到 $N$，图中共有 $M$ 条边。以顶点 $1$ 为起点，分别求到各顶点的最短路径条数。即使途经的顶点相同，只要经过的边不同，两条路径也应分别计数。

输入格式

第一行是两个正整数 $N,M$，分别为顶点数和边数。

随后 $M$ 行，每行是两个正整数 $x,y$，表示两点之间有一条边。输入可能包含自环，同一对顶点之间也可能有多条边。

输出格式

共输出 $N$ 行，每行一个非负整数。第 $i$ 行给出从顶点 $1$ 到顶点 $i$ 的最短路径条数对 $100003$ 取模的结果。不可达的顶点输出 $0$。

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

1
1
1
2
4

说明/提示

样例说明

从 $1$ 到 $5$，可以沿 $1\to2\to4\to5$ 或 $1\to3\to4\to5$ 前进。因为 $4$ 和 $5$ 之间有两条边，每种顶点序列都对应两条不同的最短路，总数为 $4$。

原题的分档数据范围如下。