P9984 [USACO23DEC] A Graph Problem P

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.

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 $N$ lines. The $i$-th line should contain the return value of the procedure when starting from node $i$.

### 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