Беси проводит каникулы на сети из \(N\) (\(2\le N\le 10^4\)) островов
помеченных \(1\dots N\) соединённых \(M\) двунаправленными мостами, каждый
из которых соединяет два острова (\(N-1\le M\le 3/2(N-1)\)). Гарантируется,
что эти мосты формируют простой граф (в частности, нет двух мостов, которые
соединяют одну и ту же пару островов, и нет моста из острова в себя же).
Также гарантируется, ни один мост не лежит более чем в одном простом цикле.
Цикл называется простым, если он не содержит повторяющиеся острова.
Беси начинает на острове \(1\) и путешествует в соответствии со следующей
процедурой:
- Если нет мостов, ведущих в соседние острова, по которым она ещё не ездила,
она завершает путешествие.
- Иначе, с вероятностью \(p_i\pmod{10^9+7}\) она завершает путешествие.
- Иначе, из всех мостов на соседние острова, по которым она ещё не перемещалась,
она равновероятно выбирает один и перемещается по нему.
Для каждого острова выведите вероятность, что она закончит своё путешествие
именно на этом острове по модулю \(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит количество независимых подтестов
\(T\)
(
\(1\le T\le 10\)). Последовательные подтесты разделены пустой строкой.
Каждый подтест имеет следующую структуру:
Первая строка содержит \(N\) и \(M\), где \(N\) - количество островов,
\(M\) - количество мостов. Гарантируется, что сумма \(N\) по всем подтестам
не превысит \(10^4\).
Вторая строка содержит \(p_1, p_2,\dots, p_N\) (\(0\le p_i<10^9+7\)).
Следующие \(M\) строк описывают мосты.
\(i\)-ая строка содержит целые числа \(u_i\) и \(v_i\) (\(1\le u_i<v_i\le N\)),
обозначающие, что \(i\)-ый мост соединяет острова \(u_i\) и \(v_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите на отдельной строке вероятности по модулю
\(10^9+7\) завершения путешествия на каждом острове от \(1\) to \(N\), разделённые
одиночными пробелами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 2
0 10 111111112
1 3
2 3
6 5
500000004 0 0 0 0 0
1 5
1 3
4 5
5 6
1 2
|
0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334
|