CF362D Fools and Foolproof Roads

你一定在地理课上听说过 Foolland。特别是，你一定知道这个国家的联邦结构已经延续了许多世纪。这个国家由 $n$ 座城市组成，部分城市之间由双向道路连接，每条道路的长度为 $l_{i}$。 傻瓜们一直在他们的土地上快乐地生活，但最近一场革命更换了国王。现在的新国王是 Vasily the Bear。Vasily 将全国的城市划分为若干个“地区”，使得同一地区的任意两座城市之间都存在一条道路路径，而不同地区的城市之间没有这样的路径。然后，Vasily 决定升级道路网络，在全国新建恰好 $p$ 条道路。修建道路的规则如下： 1. 我们选择一对不同的城市 $u$ 和 $v$ 作为新道路的两端（注意，这两座城市之间可能已存在道路）。 2. 新道路的长度确定方式如下：如果 $u$、$v$ 属于不同地区，则长度为 $min(10^9, S+1)$（$S$ 表示这两地区现有所有道路的总长度）；如果 $u$、$v$ 属于同一地区，则长度为 $1000$。 3. 按照上述规定的长度修建新道路。如果这条新路连接了两个不同的地区，则修路后这两个地区合并成一个新地区。 Vasily 希望通过修路操作，使国家最终恰好被划分为 $q$ 个地区。你的任务是为 Vasily 设计一套修建道路的方案，既满足地区数量要求，又能使新建所有道路的总长度最小。

第一行输入四个整数 $n$（$1 \leq n \leq 10^5$）、$m$（$0 \leq m \leq 10^5$）、$p$（$0 \leq p \leq 10^5$）、$q$（$1 \leq q \leq n$）——分别表示 Foolland 的城市数、已建道路数、计划修建道路数和最终需要的地区数。 接下来 $m$ 行，每行包含三个整数 $x_i$、$y_i$、$l_i$：表示城市 $x_i$ 和 $y_i$ 之间有一条长度为 $l_i$ 的道路（$1 \leq x_i, y_i \leq n, x_i \neq y_i$，$1 \leq l_i \leq 10^9$）。注意，同一对城市之间可能存在多条道路。

如果无法按要求修建道路，输出一行 "NO"（不带引号）。否则，第一行输出 "YES"（不带引号），接下来的 $p$ 行，每行输出两个不同整数，表示依次修建的道路连接的两座城市编号。若存在多种最优方案，可以输出其中任意一种。

以第一个样例为例。改革前 Foolland 被划分为四个地区。第一个地区包括城市 $1$、$2$ 和 $3$，第二个地区包括城市 $4$ 和 $6$，第三个地区包括城市 $5$、$7$、$8$，第四个地区包括城市 $9$。这些地区内道路的总长度分别为 $11$、$20$、$5$ 和 $0$。根据方案，首先在城市 $5$ 和 $9$ 之间修建一条长度为 $6$ 的道路，然后在城市 $1$ 和 $9$ 之间修建一条长度为 $23$ 的道路，因此新建道路的总长度为 $29$。 由 ChatGPT 5 翻译