Description

Given an undirected, unweighted graph with $N$ vertices and $M$ edges, where vertices are numbered $1\sim N$. Starting from vertex $1$, determine how many shortest paths there are to every other vertex.

Input Format

The first line contains $2$ positive integers $N, M$, the number of vertices and edges of the graph.

The next $M$ lines each contain $2$ positive integers $x, y$, indicating there is an edge connecting vertex $x$ and vertex $y$. Note that self-loops and multiple edges may exist.

Output Format

Output $N$ lines. The $i$-th line contains a non-negative integer: the number of different shortest paths from vertex $1$ to vertex $i$. Since the answer can be large, you only need to output $ans \bmod 100003$. If vertex $i$ is unreachable, output $0$.

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

1
1
1
2
4

Hint

From $1$ to $5$, there are $4$ shortest paths: $2$ paths $1\to 2\to 4\to 5$ and $2$ paths $1\to 3\to 4\to 5$ (because there are $2$ edges between $4$ and $5$).

Constraints:

• For $20\%$ of the testdata, $1\le N \le 100$.
• For $60\%$ of the testdata, $1\le N \le 10^3$.
• For $100\%$ of the testdata, $1\le N \le 10^6$, $1\le M \le 2\times 10^6$.

Translated by ChatGPT 5