Задача . A Graph Problem

Беси столкнулась со сложной задачей на графы - помогите ей.

Вам дан связный, ненаправленный граф с вершинами, помеченными \(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. While \(|S|<N\),
   1. �з всех ребер, которые имеют \(S\) как конечную точку, пусть \(e\) - ребро с минимальной меткой
   2. Добавляем в \(S\) конечную точку ребра \(e\), которая не содержится в \(S\).
   3. Устанавливаем \(h=10h+e\).
3. Возвращаем \(h\pmod{10^9+7}\).

ПР�МЕР ВВОДА:

3 2
1 2
2 3

ПР�МЕР ВЫВОДА:

12
12
21

ПР�МЕР ВВОДА:

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

ПР�МЕР ВЫВОДА:

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\).

ПР�МЕР ВВОДА:

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

ПР�МЕР ВЫВОДА:

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

Ответ выводите по модулю \(10^9+7\).

Problem credits: Benjamin Qi

12
12
21