You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你是一个前端程序员。有一天同事来问你这个问题：

有一张 $n$ 个点 $m$ 条边的简单无向图，每个点有一个正整数的权值。现在有人打算按一个顺序依次删除这 $n$ 个点。

定义一个连通块的权值为连通块内所有点的权值的和。他想要知道，每次删除了一个点之后，图中所有连通块权值的最大值。如果图中已经不存在连通块了，则输出 $0$。

输入格式

第一行两个正整数 $n, m$。

第二行 $n$ 个正整数 $a_1, \dots, a_n$，表示每个点的权值。

接下来$m$ 行，每行两个正整数 $u, v$，表示一条边。

下一行一个$1 ∼ n$ 的排列 $p_1,\dots, p_n$，表示每次删除的点的编号。

输出格式

输出 $n$ 行，每行一个整数。其中第 $i$ 行的数为删除了点 $p_1, \dots, p_i$ 后的答案。

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

9 
8 
4 
2 
1 
0

样例2

见附加文件 a2.in 与 a2.out。此样例满足$n, m\le 1000$。
a2.in
a2.out

数据范围与提示

对于所有的测试点, $n,m, a_i \le 10^5$。

• 对于 $30 \%$ 的数据, 满足 $n, m\le 1000$
• 另有 $20\%$ 的数据, 满足 $n,m \le 10^5, a_i=1$
• 对于 $100 \%$ 的数据, 满足 $n,m, a_i \le 10^5$