Problem Description

To broaden her math knowledge, Bessie took a graph theory course, but she got stuck on the following problem. Please help her.

You are given a connected undirected graph with nodes numbered $1 \dots N$ and edges numbered $1 \dots M$ ($2 \le N \le 2 \cdot 10^5$, $N - 1 \le M \le 4 \cdot 10^5$). The following procedure will be performed:

1. Let the set $S = \{v\}$, and the variable $h = 0$.
2. While $|S| < N$, repeat:
   1. Among the edges that have exactly one endpoint in $S$, find the one with the smallest index, and denote its index by $e$.
   2. Add the endpoint of edge $e$ that is not in $S$ into $S$.
   3. Update $h$ to $10h + e$.
3. Return $h \bmod (10^9 + 7)$.

Output all return values of this procedure.

Input Format

The first line contains $N$ and $M$. The next $M$ lines each contain the endpoints $(a_e, b_e)$ of the $e$-th edge. It is guaranteed that the graph is connected and has no multiple edges.

Output Format

Output $N$ lines. The $i$-th line should contain the return value of the procedure when starting from node $i$.

3 2
1 2
2 3

12
12
21

5 6
1 2
3 4
2 4
2 3
2 5
1 5

1325
1325
2315
2315
5132

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

Hint

Sample Explanation 2

Consider starting the procedure from $i = 3$. First, choose edge $2$, so $S = \{3, 4\}$ and $h = 2$. Then, choose edge $3$, so $S = \{2, 3, 4\}$ and $h = 23$. Next, choose edge $1$, so $S = \{1, 2, 3, 4\}$ and $h = 231$. Finally, choose edge $5$, so $S = \{1, 2, 3, 4, 5\}$ and $h = 2315$. Therefore, the answer for $i = 3$ is $2315$.

Sample Explanation 3

Make sure to take the answer modulo $10^9 + 7$.

Testdata Properties

• Testdata $4$ satisfies $N, M \le 2000$.
• Testdata $5$-$6$ satisfies $N \le 2000$.
• Testdata $7$-$10$ satisfies $N \le 10000$.
• Testdata $11$-$14$ satisfies that for all edges, $a_e + 1 = b_e$.
• Testdata $15$-$23$ has no additional constraints.

Translated by ChatGPT 5