CF587D Duff in Mafia
题目描述
Duff 是她所在国家 Andarz Gu 的黑手党头目之一。Andarz Gu 有 $n$ 个城市（编号为 $1$ 到 $n$），通过 $m$ 条双向道路（编号为 $1$ 到 $m$）连接。
每条道路都有一个摧毁时间和一个颜色。第 $i$ 条道路连接城市 $v_i$ 和 $u_i$，颜色为 $c_i$，摧毁时间为 $t_i$。
黑手党想要摧毁 Andarz Gu 的一个匹配。一个匹配是若干道路的集合，集合中没有任何两条道路有公共端点。他们可以并行炸毁这些道路，即总摧毁时间为所有被选择道路的最大摧毁时间。
他们希望满足以下两个条件：
1. 剩余道路形成一个合法着色。
2. 匹配的摧毁时间最小。
所谓剩余道路形成合法着色，就是任何两个同色的道路没有公共端点，换句话说，每种颜色的边都构成一个匹配。
黑手党中没人会编程，所以 Duff 向你寻求帮助。请你帮助她判断是否有可能满足上述条件，并求出该匹配（或指出不可能）。
输入格式
输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5 \times 10^4$，$1 \le m \le 5 \times 10^4$），分别表示城市数和道路数。
接下来的 $m$ 行，每行包含四个整数 $v_i, u_i, c_i, t_i$（$1 \le v_i,u_i \le n$，$v_i \ne u_i$，$1 \le c_i, t_i \le 10^9$，$1 \le i \le m$），分别表示第 $i$ 条道路连接的城市编号、颜色和摧毁时间。
输出格式
第一行输出若能满足第一个条件则输出 “Yes”，否则输出 “No”。
若可以，请在第二行输出两个整数 $t$ 和 $k$，其中 $t$ 为最小摧毁时间，$k$ 为要摧毁道路的数量。
第三行输出 $k$ 个两两不同的整数，表示要摧毁的道路编号（从 1 开始，按输入顺序编号），顺序任意。
如果有多组解，输出任意一组均可。
说明/提示
第一个样例的 Andarz Gu 的图如下：
一种方案是摧毁带有叉号的道路。
第二个样例的 Andarz Gu 的图如下：
由 ChatGPT 5 翻译