你一定在地理课上听说过有关愚人节的一切。具体来说,你必须知道这个国家的联邦结构几个世纪以来都是一样的。该国家由 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。