SP25474 TAP2015D - Happiness for all

分离主义国家 Nlogonia 有 $N$ 个城市，编号为 $1$ 到 $N$。一些城市通过高速公路互相连接，如果存在从城市 $A$ 到城市 $B$ 的高速公路，则表示可以互相往返。 我们称，城市 $i$ 的居民可以访问城市 $j$ 的居民，如果存在一系列不同的城市 $c_1, c_2, \ldots, c_m$（其中 $m \geq 2$），满足 $c_1 = i$ 且 $c_m = j$，并且对于每一个 $k = 1, 2, \ldots, m-1$，城市 $c_k$ 和城市 $c_{k+1}$ 之间都有高速公路。 Nlogonia 的人民非常友善，他们在能去拜访的城市中都有朋友。但他们也有些懒，只有通过一条直接的高速公路就能到达朋友所在的城市，才能让他们感到满意。 为了防止 Nlogonia 分裂，女王打算进行一些基础设施建设，让所有居民都满意。一种方法是在城市之间修建新的高速公路，每条高速公路的建设成本为 $R$。由于这样做开销很大，另一种选择是在城市建造体育场。建造一个体育场的成本为 $E$，而且可以立刻让该城市的所有居民满意。 但需注意，Nlogonia 的居民有点嫉妒，如果他们的城市没有体育场而他们朋友的城市有，他们将永远不会满意。请帮女王算出使所有人满意的最小建设成本。

输入文件包含多个测试用例。每个测试用例第一行为四个整数 $N, M, R$ 和 $E$，其中 $N$ 是城市数量（$2 \leq N \leq 10^5$），$M$ 是已有的高速公路数量（$1 \leq M \leq 10^5$）。$R$ 和 $E$ 分别表示建造高速公路和体育场的费用（$1 \leq R, E \leq 10^9$）。接下来 $M$ 行描述已存在的高速公路，每行有两个整数 $A$ 和 $B$，表示连接城市 $A$ 和 $B$ 的高速公路（$1 \leq A, B \leq N$, 且 $A \neq B$）。

对于每个测试用例，输出一个整数，代表让所有 Nlogonia 的居民满意所需的最小建设成本。 **本翻译由 AI 自动生成**