新亚（New Asia）王国有N 个村庄，由M 条道路连接。其中一些道路是鹅
卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去
王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。
国王已经决定保持尽可能少的道路免费，但是每两个不同的村庄之间都应该
由一条且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需
要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好
K 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路如图3(a)所示。如果国王希望保持两
条鹅卵石路免费，那么可以如图3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5)
免费。该方案满足了国王的要求，因为：(1)每两个村庄之间都有一条由免费道
路组成的路径；(2)免费的道路已经尽可能少；(3)方案中刚好有两条鹅卵石道路
(2, 3)和(3, 4)。

图3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路，虚线标注
的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免
费道路。

给定一个关于新亚王国村庄和道路的描述以及国王决定保持免费的鹅卵石
道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果
存在则任意输出一个方案。