← 返回题目列表

Codeforces · 362/D

D. 傻瓜和万无一失的道路

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

你一定在地理课上听说过有关愚人节的一切。具体来说,你必须知道这个国家的联邦结构几个世纪以来都是一样的。该国家由 n 个城市组成,一些城市对通过双向道路连接,每条道路由其长度 li 描述。

傻瓜们快乐地生活在他们的土地上,但最近的一场革命改变了国王。现在的国王是熊瓦西里。瓦西里将乡村城市划分为区域,使得同一区域的任何两个城市之间都有一条沿着道路的路径,而不同区域的任何两个城市之间没有这样的路径。然后瓦西里决定升级道路网络并在该国修建 p 条新道路。修路的过程是这样的:

1. 我们选择一对不同的城市 u, v,将通过一条新道路连接起来(此时,这些城市之间可能已经有一条道路)。
2.我们定义新道路的长度:如果城市u、v属于不同的区域,则长度计算为min(109, S + 1)(S - 链接区域中存在的所有道路的总长度),否则我们假设长度等于1000。
3. 我们在选定的城市之间修建一条指定长度的道路。如果新道路连接两个不同的区域,则在道路建成后,这些区域将合并为一个新区域。

Vasily 希望道路建设过程能够形成由 q 个区域组成的国家。你的任务是为瓦西里提出这样的道路建设计划,使其满足要求并最大限度地减少已建道路的总长度。

输入

第一行包含四个整数n(1≤n≤105)、m(0≤m≤105)、p(0≤p≤105)、q(1≤q≤n)——愚人国的城市数量、现有道路数量、计划建设道路数量和所需区域数量。

接下来的 m 行描述了道路升级开始时存在的道路。每行包含三个整数 xi, yi, li: xi, yi — 这条道路连接的城市编号 (1 ≤ xi, yi ≤ n, xi ≠ yi),li — 道路长度 (1 ≤ li ≤ 109)。请注意,一对城市可以通过多条道路连接。

输出

如果不可能按照要求的方式建造道路,则打印单个字符串“NO”(不带引号)。否则,在第一行打印单词“YES”(不带引号),并在接下来的 p 行中打印道路施工计划。计划的每一行必须由两个不同的整数组成,给出由道路连接的城市的数量。道路必须按照需要施工的顺序出现在计划中。如果有多个最优解,可以打印任意一个。

示例

输入 #1

9 6 2 2
1 2 2
3 2 1
4 6 20
1 3 8
7 8 3
5 7 2

输出 #1

YES
9 5
1 9

输入 #2

2 0 1 2

输出 #2

NO

输入 #3

2 0 0 2

输出 #3

YES

注意

考虑第一个样本。改革前,愚国由四个地区组成。第一个区域包含城市 1、2、3,第二个区域包含城市 4、6,第三个区域包含城市 5、7、8,第四个区域包含城市 9。这些城市的道路总长度分别为 11、20、5 和 0。根据规划,我们首先在城市5和城市9之间修建长度为6的道路,然后在城市1和城市9之间修建长度为23的道路。因此,已修建的道路总长度为29。