#P3624. [Apio2008]免费道路
[Apio2008]免费道路
[APIO2008] 免费道路
题目描述
新亚王国有 个村庄,由 条道路连接。道路分为鹅卵石路和水泥路。维持道路免费通行需要花钱,国王决定只保留尽可能少的免费道路,同时保证任意两个不同村庄之间恰有一条由免费道路组成的路径。国王还要求免费道路中恰有 条鹅卵石路。
例如,图 1(a) 给出了五个村庄之间的道路。若 ,可以留下连接 、、 和 的四条道路,如图 1(b)。其中 和 是鹅卵石路。

图中的实线表示水泥路,虚线表示鹅卵石路。图 1(b) 只画出了免费的道路。
给定道路及 ,判断是否存在符合要求的方案。若有,请输出任意一个方案。
输入格式
第一行三个整数 。
接下来 行,第 行用三个整数 描述一条连接村庄 与 的道路。村庄编号为 至 。 表示鹅卵石路, 表示水泥路。任意一对村庄之间至多有一条道路。
输出格式
无解时输出一行 no solution。
有解时,逐行输出保留的每条道路,每行复用该道路在输入中的三个整数及其顺序。各行顺序任意。
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
3 2 0
4 3 0
1 2 1
5 3 1
数据范围与评分
,,。
每个测试情形独立判定,正确得该情形的满分。原赛有 分的数据满足 。