【问题描述】

Farmer John 有 N 个农场，编号为 1 ~ N。每个农场里住着一头奶牛，农场 i 住着的奶牛编号也为 i。

有 M 条双向通行的道路。每条道路的长度均为 1。

奶牛 Bessie 家住 1 号农场。她很喜欢串门。而且，为了节省体力，她总是走最短路。

她想知道自己到奶牛 i 家的最短路有多少条？

你能帮助她吗？

【输入格式】

第一行：两个整数 N, M

接下来 M 行：每行两个整数 u, v，表示农场 u 和 v 之间有一条道路。可能有一条道路连接自身（自环），两个农场间可能有多条道路（重边）。

【输出格式】

共 N 行，每行一个整数，第 i 行的整数表示从农场 1 到农场 i 的最短路条数。答案可能很大，你需要将其对 100003 取模后输出。如果无法到达农场 i，则在对应行输出 0。

（注：第一行输出 1，表示农场 1 到农场 1 的最短路条数有 1 条。）

【输入样例】

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

【输出样例】

1
1
1
2
4

【数据范围】

20% 的数据：N ≤ 100；

60% 的数据：N ≤ 1000；

100% 的数据：1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000。