Problem Description

To enrich her mathematical knowledge, Bessie has enrolled in a graph theory course. She has found herself stuck on the following problem. Please help her!

Given a connected undirected graph with nodes numbered from $1$ to $N$ and edges numbered from $1$ to $M$ ($2 \le N \le 2 \cdot 10^5$, $N - 1 \le M \le 4 \cdot 10^5$), the following operations will be performed:

1. Initialize the set $S = \{v\}$ and the variable $h = 0$.
2. While $|S| < N$, repeat:
3. Find the edge with the smallest number among those with only one vertex in set $S$, and denote its number as $e$.
4. Add the vertex of edge $e$ that is not in set $S$ to set $S$.
5. Update $h$ to $10h + e$.
6. Return the value of $h$ modulo $10^9 + 7$.

Output the complete return values of this process.

Input Format

The first line contains $N$ and $M$. The next $M$ lines each contain the vertices $(a_e, b_e)$ of the $e$-th edge, ensuring the graph is connected and has no duplicate edges.

Output Format

Output $N$ lines, where the $i$-th line contains the return value starting from node $i$.

Sample Input and Output

Sample Input #1

3 2
1 2
2 3

Sample Output #1

12
12
21

Sample Input #2

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

Sample Output #2

1325
1325
2315
2315
5132

Sample Input #3

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

Sample Output #3

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

Notes/Hints

Sample Explanation 2

Consider starting the process at $i = 3$. Initially, choose edge $2$, $S = \{3, 4\}$, $h = 2$. Then, choose edge $3$, $S = \{2, 3, 4\}$, $h = 23$. Next, choose edge $1$, $S = \{1, 2, 3, 4\}$, $h = 231$. Finally, choose edge $5$, $S = \{1, 2, 3, 4, 5\}$, $h = 2315$. Thus, the answer for $i = 3$ is $2315$.

Sample Explanation 3

Ensure the answer is taken modulo $10^9 + 7$.

Test Case Properties

• Test case $4$ satisfies $N, M \le 2000$.
• Test cases $5-6$ satisfy $N \le 2000$.
• Test cases $7-10$ satisfy $N \le 10000$.
• Test cases $11-14$ satisfy $a_e + 1 = b_e$ for all edges.
• Test cases $15-23$ have no additional restrictions.

见题面 Input 部分

见题面 Output 部分