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}$.
Determine all the return values of this process.
Input
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
Output $N$ lines, where the $i$th line should contain the return value of the process starting at vertex $i$.
Examples
Input 1
3 2 1 2 2 3
Output 1
12 12 21
Input 2
5 6 1 2 3 4 2 4 2 3 2 5 1 5
Output 2
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$.
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
Output 3
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