← 返回题目列表

Codeforces · 587/D

D. 达夫在黑手党

中文机器翻译题面 查看原题

Duff 是她所在国家 Andarz Gu 的黑手党头目之一。安达兹区有 n 个城市(编号为 1 到 n),由 m 条双向道路(编号为 1 到 m)连接。

每条路都有破坏时间和颜色。第i条路连接城市vi和ui,其颜色为ci,破坏时间为ti。

黑手党想要破坏安达兹古中的一场比赛。匹配是道路的子集,使得该子集中没有两条道路具有公共端点。他们可以同时破坏这些道路,即。 e.总破坏时间是所有选定道路的破坏时间中的最大值。

他们希望满足两个条件:

1. 其余道路形成适当的着色。
2. 该匹配的破坏时间被最小化。

破坏此匹配后的剩余道路形成正确的着色当且仅当没有两条相同颜色的道路具有相同的端点,或者换句话说,每种颜色的边缘应形成匹配。

Mafia 中没有程序员。这就是达夫请求你帮助的原因。请帮助她并确定要破坏哪个匹配才能满足这些条件(或说明这是不可能的)。

输入

输入的第一行包含两个整数 n 和 m(2 ≤ n ≤ 5 × 104 和 1 ≤ m ≤ 5 × 104)、该国的城市数量和道路数量。

接下来的 m 行包含道路。其中第 i 个包含四个整数 vi、ui、ci 和 ti(对于每个 1 ≤ i ≤ m,1 ≤ vi、ui ≤ n、vi ≠ ui 且 1 ≤ ci、ti ≤ 109)。

输出

在输入的第一行中,如果可以满足第一个条件,则打印“Yes”(不带引号),否则打印“No”(不带引号)。

如果可以的话,那么你必须在第二行打印两个整数t和k,最小破坏时间和匹配的路数($$0 \leq k \leq \left[\frac{n}{2}\right]$$)。

在第三行中打印 k 个由空格分隔的不同整数,以任意顺序匹配的道路索引。道路按照其在输入中出现的顺序从 1 开始编号。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5 7
2 1 3 7
3 1 1 6
5 4 1 8
4 5 1 1
3 2 2 3
4 5 2 5
2 3 2 4

输出 #1

Yes
3 2
4 5

输入 #2

3 5
3 2 1 3
1 3 1 1
3 2 1 4
1 3 2 2
1 3 2 10

输出 #2

No

注意

第一个示例案例中Andarz Gu的图表如下:

解决方案是用十字架破坏道路。

第二个示例案例中Andarz Gu的图表如下: