[R61F]图 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

给定一个 $n$ 个点、$m$ 条边的无向简单图 $G$，图中没有自环和重边。

每个点 $i$ 有一个权值 $w_i$。

现在需要将所有点划分成两个有序点集 $S_1, S_2$，满足：

$$S_1 \cap S_2 = \varnothing, \qquad S_1 \cup S_2 = \{1, 2, \dots, n\}$$

也就是说，每个点必须恰好属于 $S_1$ 或 $S_2$ 中的一个。

我们称一个划分 $(S_1, S_2)$ 是合法的，当且仅当 $S_1$ 和 $S_2$ 在图 $G$ 中均为团。

这里，团指的是一个点集中的任意两个不同点之间都有边。空集和单点集也视为团。

一个合法划分的价值定义为 $S_1$ 中所有点的权值之和：

$$V(S_1) = \sum_{v \in S_1} w_v$$

对于每一个 $k = 1, 2, \dots, n$，请你求出所有满足 $|S_1| = k$ 的合法划分的价值之和。

由于答案可能很大，请对 $10^9 + 7$ 取模后输出。

格式

输入格式

第一行输入两个整数 $n, m$，表示图 $G$ 的点数和边数。

第二行输入 $n$ 个整数 $w_1, w_2, \dots, w_n$，表示每个点的权值。

接下来 $m$ 行，每行输入两个整数 $u, v$，表示 $G$ 中存在一条无向边 $(u, v)$。

输出格式

输出一行 $n$ 个整数。整数之间使用空格分隔。

第 $k$ 个整数表示所有满足 $|S_1| = k$ 的合法划分的价值之和，答案对 $10^9 + 7$ 取模。

样例

样例输入 #1

5 7
1 2 3 4 5
1 3
1 4
1 5
2 3
2 4
2 5
3 5

样例输出 #1

0 11 19 0 0

样例输入 #2

3 0
5 6 7

样例输出 #2

0 0 0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$
$1$	$20$	$15$
$2$	$80$	$3000$

对于 $100\%$ 的数据，$1 \le n \le 3000$，$0 \le m \le \frac{n(n-1)}{2}$，$1 \le w_i \leq 10^9$，$1 \le u < v \le n$，保证输入的图 $G$ 无自环、无重边。