A Graph Problem

문제

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 N1\backslash dots\; N$ and edges labeled $1\dots M1\backslash dots\; M$ ($2\le N\le 2\cdot {10}^{5}2\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$, $N-1\le M\le 4\cdot {10}^{5}N-1\backslash le\; M\backslash le\; 4\backslash cdot\; 10^5$). For each vertex $vv$ in the graph, the following process is conducted: ​

1. Let $S=\{v\}S=\backslash \{v\backslash \}$ and $h=0h=0$.
2. While , ​
   1. Out of all edges with exactly one endpoint in $SS$, let $ee$ be the edge with the minimum label.
   2. Add the endpoint of $ee$ not in $SS$ to $SS$.
   3. Set $h=10h+eh=10h+e$.
3. Return $h(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)h\backslash pmod\{10^9+7\}$.

​ Determine all the return values of this process.

입력

The first line contains $NN$ and $MM$. ​ Then follow $MM$ lines, the $ee$th containing the endpoints $(a_e,b_e)(a\_e,b\_e)$ of the $ee$th edge (). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.

출력

Output $NN$ lines, where the $ii$th line should contain the return value of the process starting at vertex $ii$.