为了提高数学知识，Bessie 正在学习一门图论课程，但她被以下问题难住了。请帮帮她！

给定一个连通无向图，顶点编号为 $1\dots N$，边编号为 $1\dots M$ ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$)。对于图中的每个顶点 $v$，执行以下过程：

1. 令 $S=\{v\}$ 且 $h=0$。
2. 当 $|S|
3. 在所有恰好有一个端点在 $S$ 中的边中，令 $e$ 为编号最小的边。
4. 将 $e$ 中不在 $S$ 中的端点加入 $S$。
5. 令 $h=10h+e$。

确定该过程的所有返回值。

第一行包含 $N$ 和 $M$。

接下来 $M$ 行，第 $e$ 行包含第 $e$ 条边的端点 $(a_e,b_e)$ ($1\le a_e

输出 $N$ 行，其中第 $i$ 行应包含从顶点 $i$ 开始执行该过程的返回值。

样例

输入格式 1

3 2
1 2
2 3

输出格式 1

12
12
21

输入格式 2

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

输出格式 2

1325
1325
2315
2315
5132

说明

考虑从 $i=3$ 开始。首先，我们选择边 $2$，此时 $S = \{3, 4\}$ 且 $h = 2$。其次，我们选择边 $3$，此时 $S = \{2, 3, 4\}$ 且 $h = 23$。第三，我们选择边 $1$，此时 $S = \{1, 2, 3, 4\}$ 且 $h = 231$。最后，我们选择边 $5$，此时 $S = \{1, 2, 3, 4, 5\}$ 且 $h = 2315$。因此，$i=3$ 的答案为 $2315$。

输入格式 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

输出格式 3

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

请确保输出对 $10^9+7$ 取模后的答案。

子任务

• $N,M\le 2000$
• $N\le 2000$
• $N\le 10000$
• 对于所有 $e$，$a_e+1=b_e$
• 无额外限制。