秘纹序列的极致共振

题目描述

在古时代的“恒谒宫”中，流传着一段被称作 秘纹序列 的数字刻印。 它由 $n$ 个符号构成，每个符号蕴藏着独特的能量值，被记录为数组 $nums$。

根据祭司的记录，秘纹序列的 共振强度 依以下方式计算： res = nums[1] - nums[2] + nums[3] - nums[4] + ...（奇数位取正、偶数位取负）。

然而，秘纹石阵并未凝固；部分符号之间被古老的 迁位纹路 所连接，即 $nums$索引为 $i$ 与 $j$ 连接。 每条迁位纹路是一条只在特定符号之间生效的秘法，通过它，你可以令这两个位置上的符号 对换本源——且次数不受限制，即 $nums$ 索引为 $i$ 与 $j$ 上的元素可以互换。

迁位纹路之间相互交错，形成一个神秘的“位格连结网”。 在这个网允许的范围内，你可以对被连接的符号进行 任意顺序、任意次数的迁位术。

你的任务是：在遵循所有迁位纹路的情况下，使秘纹序列的共振强度达到可能的最大值。

形式化的，给定一个长度为 $n$ 的整数数组 $nums$ 和一个二维整数数组 $pairs$，其中 $pairs[i] = [p_i, q_i]$ 表示 $nums$ 索引为 $p_i$ 与 $q_i$ 上的元素可以互换。 你可以任意次交换 $nums$ 中由 $pairs$ 所连接的索引对上的元素。 你需要求出在进行任意次交换后，$nums$ 的 最大交替和。

输入格式

第一行输入两个整数 $n$ 和 $m$,分别表示数组大小和符号相连数。 $(1 \leq n \leq 10^{6},0 \leq m \leq 10^{5})$

第二行输入 $n$ 个整数，表示数组 $nums$ 的值。$(1 \leq nums_i \leq 10^{9})$ 接下来 $m$ 行，每行两个整数 $p$ 和 $q$，表示 $nums$ 索引为 $p$ 与 $q$ 上的元素可以互换 $(1 \leq p, q \leq n, p \neq q)$。

数据保证 $[p_i, q_i] \neq [p_j, q_j]$（$1 \leq i,j \leq m$）。

输出格式

输出一个整数，表示秘纹序列能够达到的 最大共振强度。

样例 1

3 2
1 2 3
1 2
2 3

4

样例 2

3 1
1 2 3
2 3

2

提示

当 nums 为 [2, 1, 3] 或 [3, 1, 2] 时，可以实现最大交替和。例如，你可以通过以下方式得到 nums = [2, 1, 3]。

• 交换 nums[1] 和 nums[3]。此时 nums 为 [3, 2, 1]。
• 交换 nums[2] 和 nums[3]。此时 nums 为 [3, 1, 2]。
• 交换 nums[1] 和 nums[3]。此时 nums 为 [2, 1, 3]。