Description

Given an undirected and unweighted graph with $N$ vertices and $M$ edges, where the vertices are labeled from $1$ to $N$. Determine the number of shortest paths from vertex $1$ to each of the other vertices.

Input Format

The first line contains two positive integers $N$ and $M$, representing the number of vertices and edges in the graph, respectively.

The next $M$ lines each contain two positive integers $x$ and $y$, indicating an edge between vertex $x$ and vertex $y$. Note that there may be self-loops and multiple edges.

Output Format

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

Sample 1

There are $4$ shortest paths from $1$ to $5$: $2$ paths via $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ and $2$ paths via $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ (since there are $2$ edges between $4$ and $5$).

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

1
1
1
2
4

Data Range and Hints

For $20\%$ of the data, $N \le 100$;

For $60\%$ of the data, $N \le 1000$;

For $100\%$ of the data, $1 \le N \le 100000, 0 \le M \le 200000$.