当前没有测试数据。

题目描述

给定一张 $n$ 个顶点、$m$ 条边的连通无向简单图。顶点 $i$ 上有一个标记 $c_i \in \{0,1\}$。

一条边称为桥，当且仅当删除这条边后，图恰好分成两个连通分量。题目保证图中至少存在一座桥。

对于每个顶点 $x\ (1 \le x \le n)$，其最大价值定义为独立进行如下过程能得到的最大值：

1. 把 $c_x$ 翻转，即 $0$ 变为 $1$，$1$ 变为 $0$；
2. 选择图中的一座桥并删除；
3. 设删除后两个连通分量中标记为 $1$ 的顶点数分别为 $p$ 和 $q$，得到价值 $|p-q|$。

请注意：不同 $x$ 的过程互相独立：计算下一个顶点时，所有标记恢复为输入中的初始状态。

现在你需要对于每个顶点求出其最大价值。

输入格式

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

第二行 $n$ 个整数 $c_1,c_2,\dots,c_n$。

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

输出格式

输出一行 $n$ 个整数，第 $x$ 个整数表示翻转顶点 $x$ 后的最大价值。

样例

7 8
1 0 1 0 1 0 0
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 5

0 2 0 2 2 0 0

样例解释 图中的桥为 $(3,4)$ 和 $(4,5)$。 例如翻转顶点 $4$ 后共有四个 $1$。删除桥 $(4,5)$ 时，两侧分别有三个和一个 $1$，价值为 $2$。

数据规模与约定

• $2 \le n \le 2 \times 10^5$；
• $n-1 \le m \le 4 \times 10^5$；
• $c_i \in \{0,1\}$；
• 输入图连通、无自环、无重边，并且至少含有一座桥；

共 20 个测试点，每个测试点 5 分。下表各行所列测试点共同满足对应的额外约束。下表中的“桥树”指把每个删除全部桥后得到的连通块缩成一个点，再用原图中的桥连接所得的树。

原题链接

原题链接