题目描述

给出一个无向图，求从结点 1 到每个结点的最短路线条数，答案对 100003 取模。不可达结点输出 0。

输入格式

第一行 $n,m$，随后 $m$ 行道路 $u,v$。

输出格式

输出 $n$ 行，第 $i$ 行为到结点 $i$ 的最短路线条数。

样例

4 4
1 2
1 3
2 4
3 4

1
1
1
2

数据规模与约定

$1\le n\le200000$，$0\le m\le300000$；可能有重边。