Shortest Path Counting

Problem Description

You are given an undirected, unweighted graph with $N$ vertices and $M$ edges.

For each vertex other than vertex $1$, count how many different shortest paths lead from vertex $1$ to it.

Input Format

The first line contains two positive integers $N, M$.

Each of the next $M$ lines contains two positive integers $x, y$, meaning there is an edge from vertex $x$ to vertex $y$ (multiple edges and self-loops may exist).

Output Format

Output $N$ lines, each containing a non-negative integer. The $i$-th line is the number of different shortest paths from vertex $1$ to vertex $i$.

Since the answer may be large, output the result modulo $100003$.

If vertex $1$ cannot reach vertex $i$, output $0$.

Sample Input

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

Sample Output

1
1
1
2
4

Constraints

$1 \le N \le 10^6$, $1 \le M \le 2 \times 10^6$.

Hint

Because the amount of data is large, please use fast input/output methods.