## USACO 2023 December Contest, Platinum

## Problem 2. A Graph Problem

Contest has ended.

**Log in to allow submissions in analysis mode**

To improve her mathematical knowledge, Bessie has been taking a graph theory course and finds herself stumped by the following problem. Please help her!

You are given a connected, undirected graph with vertices labeled $1\dots N$ and edges labeled $1\dots M$ ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$). For each vertex $v$ in the graph, the following process is conducted:

- Let $S=\{v\}$ and $h=0$.
- While $|S|<N$,
- Out of all edges with exactly one endpoint in $S$, let $e$ be the edge with the minimum label.
- Add the endpoint of $e$ not in $S$ to $S$.
- Set $h=10h+e$.

- Return $h\pmod{10^9+7}$.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ and $M$. Then follow $M$ lines, the $e$th containing the endpoints $(a_e,b_e)$ of the $e$th edge ($1\le a_e<b_e\le N$). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.#### OUTPUT FORMAT (print output to the terminal / stdout):

Output $N$ lines, where the $i$th line should contain the return value of the process starting at vertex $i$.#### SAMPLE INPUT:

3 2 1 2 2 3

#### SAMPLE OUTPUT:

12 12 21

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

1325 1325 2315 2315 5132

Consider starting at $i=3$. First, we choose edge $2$, after which $S = \{3, 4\}$ and $h = 2$. Second, we choose edge $3$, after which $S = \{2, 3, 4\}$ and $h = 23$. Third, we choose edge $1$, after which $S = \{1, 2, 3, 4\}$ and $h = 231$. Finally, we choose edge $5$, after which $S = \{1, 2, 3, 4, 5\}$ and $h = 2315$. The answer for $i=3$ is therefore $2315$.

#### SAMPLE INPUT:

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:

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

Make sure to output the answers modulo $10^9+7$.

#### SCORING:

- Input 4: $N,M\le 2000$
- Inputs 5-6: $N\le 2000$
- Inputs 7-10: $N\le 10000$
- Inputs 11-14: $a_e+1=b_e$ for all $e$
- Inputs 15-23: No additional constraints.

Problem credits: Benjamin Qi