CF587D.Duff in Mafia

Duff is one if the heads of Mafia in her country, Andarz Gu. Andarz Gu has n cities (numbered from 1 to n) connected by m bidirectional roads (numbered by 1 to m).

Each road has a destructing time, and a color. i-th road connects cities v__i and u__i and its color is c__i and its destructing time is t__i.

Mafia wants to destruct a matching in Andarz Gu. A matching is a subset of roads such that no two roads in this subset has common endpoint. They can destruct these roads in parallel, i. e. the total destruction time is a maximum over destruction times of all selected roads.

They want two conditions to be satisfied:

1. The remaining roads form a proper coloring.
2. Destructing time of this matching is minimized.

The remaining roads after destructing this matching form a proper coloring if and only if no two roads of the same color have same endpoint, or, in the other words, edges of each color should form a matching.

There is no programmer in Mafia. That's why Duff asked for your help. Please help her and determine which matching to destruct in order to satisfied those conditions (or state that this is not possible).

达芙是安达尔兹古国黑手党的一位头目。安达尔兹古国有 $n$ 座城市（编号从 $1$ 到 $n$），由 $m$ 条双向道路（编号从 $1$ 到 $m$）连接。

每条道路具有一个破坏耗时和一种颜色。第 $i$ 条道路连接城市 $v_i$ 和 $u_i$，其颜色为 $c_i$，破坏耗时为 $t_i$。

黑手党希望在安达尔兹古国中破坏一个匹配（matching）。匹配是指道路的一个子集，其中任意两条道路均无公共端点。这些道路可并行破坏，即总破坏耗时等于所选道路中最大的单条破坏耗时。

他们希望满足以下两个条件：

1. 剩余的道路构成一个合法的边染色（proper coloring）；
2. 该匹配的破坏耗时最小。

破坏该匹配后剩余的道路构成合法边染色，当且仅当：任意两条同色道路不共享端点；换言之，每种颜色对应的所有边自身构成一个匹配。

黑手党中没有程序员，因此达芙向你求助。请帮助她确定应破坏哪一个匹配以满足上述条件（或判定该问题无解）。

The first line of input contains two integers n and m (2 ≤ n ≤ 5 × 104 and 1 ≤ m ≤ 5 × 104), number of cities and number of roads in the country.

The next m lines contain the the roads. i - th of them contains four integers v__i, u__i, c__i and t__i (1 ≤ v__i, u__i ≤ n, v__i ≠ u__i and 1 ≤ c__i, t__i ≤ 109 for each 1 ≤ i ≤ m).

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 5 \times 10^4$，$1 \leq m \leq 5 \times 10^4$），分别表示国家中的城市数量和道路数量。

接下来的 $m$ 行描述了这些道路。其中第 $i$ 行包含四个整数 $v_i$、$u_i$、$c_i$ 和 $t_i$（对每个 $1 \leq i \leq m$，满足 $1 \leq v_i,\,u_i \leq n$，$v_i \neq u_i$，且 $1 \leq c_i,\,t_i \leq 10^9$）。

In the first line of input, print "Yes" (without quotes) if satisfying the first condition is possible and "No" (without quotes) otherwise.

If it is possible, then you have to print two integers t and k in the second line, the minimum destructing time and the number of roads in the matching ().

In the third line print k distinct integers separated by spaces, indices of the roads in the matching in any order. Roads are numbered starting from one in order of their appearance in the input.

If there's more than one solution, print any of them.

在输入的第一行中，如果满足第一个条件是可能的，则输出“Yes”（不带引号），否则输出“No”（不带引号）。

如果可行，则在第二行输出两个整数 $t$ 和 $k$，分别为最小破坏时间与匹配中的道路数量（）。

在第三行输出 $k$ 个互不相同的整数，以空格分隔，表示匹配中各条道路的编号（顺序任意）。道路编号从 1 开始，按其在输入中出现的顺序依次编号。

若存在多个解，输出任意一个即可。

Graph of Andarz Gu in the first sample case is as follows:

A solution would be to destruct the roads with crosses.

Graph of Andarz Gu in the second sample case is as follows:

第一个样例的安达尔兹·古图如下所示：

一种可行方案是摧毁带叉号的道路。

第二个样例的安达尔兹·古图如下所示：