← 返回题目列表

AtCoder · apc001_d

D. 森林

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

你得到了一片森林 N 顶点和 M 边缘。顶点已编号 0 通过 N-1。 边缘以以下格式给出 (x_i,y_i),这意味着顶点 x_i 和 y_i 通过边连接。

每个顶点 i 有一个值 a_i。 您想要在给定的森林中添加边,以便森林相互连接。 要添加边,请选择两个不同的顶点 i 和 j,然后跨过一条边 i 和 j。 此操作成本 a_i + a_j 美元,然后 Vertex 可以再次选择 i 也不 j 。

求使森林连通所需的最低总成本,或打印 Impossible 如果不可能的话。

约束

  • 1 ≤ N ≤ 100,000
  • 0 ≤ M ≤ N-1
  • 1 ≤ a_i ≤ 10^9
  • 0 ≤ x_i,y_i ≤ N-1
  • 给定的图是一个森林。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
a_0 a_1 .. a_{N-1}
x_1 y_1
x_2 y_2
:
x_M y_M

输出

打印连接森林所需的最低总成本,或打印 Impossible 如果不可能的话。


示例输入 1

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

示例输出 1

7

如果我们连接顶点 0 和 5,图变成连通的,成本为 1 + 6 = 7 美元。


示例输入 2

5 0
3 1 4 1 5

示例输出 2

Impossible

我们无法将图连接起来。


示例输入 3

1 0
5

示例输出 3

0

该图已经连接,因此我们不需要添加任何边。