P3623 [APIO2008] 免费道路

新亚（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) 一个保持两条鹅卵石路免费的维护方案。图中仅标出了免费道路。 给定一个关于新亚王国村庄和道路的述以及国王决定保持免费的鹅卵石道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果存在则任意输出一个方案。

无

无

### 数据范围 对于 $100\%$ 的数据。保证 $1 \le N \le 2 \times 10^4$，$1 \le M \le 10^5$，$0 \le K \le N-1$。