D. Duff в мафии
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Duff — одна из глав мафии в своей стране Andarz Gu. В Andarz Gu n городов (пронумерованных от 1 до n), соединенных m двусторонними дорогами (пронумерованными от 1 до m).

У каждой дороги есть два специальных параметра — время её разрушения и цвет. i-я дорога соединяет города vi и ui, её цвет — ci, а время разрушения — ti.

Мафия хочет разрушить паросочетание в Andarz Gu. Паросочетание — это подмножество дорог, такое, что никакие две дороги в этом подмножестве не имеют один и тот же город в качестве конца. Дороги можно разрушать параллельно, то есть, время полного разрушения набора дорог определяется как максимум среди времен разрушения всех дорог в наборе.

Имеются два условия:

  1. Оставшиеся дороги образуют в правильную раскраску.
  2. Время разрушения этого паросочетания как можно меньше.

После разрушения паросочетания оставшиеся дороги образуют правльную раскраску тогда и только тогда, когда никакие две дороги одного и того же цвета не имеют один и тот же город в качестве конца. Иными словами, для каждого из оставшихся цветов рёбра с этим цветом должны формировать паросочетание.

У мафии нет программиста в штате. Поэтому Duff попросила вас помочь ей. Пожалуйста, помогите ей и определите, какое паросочетание надо уничтожить, чтобы удовлетворить вышеописанным условиям, либо скажите, что это невозможно.

Входные данные

В первой строке входа записаны два целых числа, n и m (2 ≤ n ≤ 5 × 104 и 1 ≤ m ≤ 5 × 104), количество городов и количство дорог в стране.

В следующих m естроках записаны дороги. В i-й из них записано четыре целых числа vi, ui, ci и ti (1 ≤ vi, ui ≤ n, vi ≠ ui и 1 ≤ ci, ti ≤ 109 для каждого 1 ≤ i ≤ m).

Выходные данные

В первой строке входа выведите "Yes" (без кавычек), если требуемое паросочетание существует, и "No" (без кавычек) в противном случае.

Если возможно достичь требуемого, то надо вывести два целых числа t и k на второй строке, минимальное время разрушения и количество дорог в паросочетании () соответстенно.

В третьей строке выведите k различных целых чисел — номера дорог искомого паросочетания. Номера могут следовать в любом порядке. Дороги нумеруются с единицы в порядке следования во входных данных.

Если возможных ответов несколько, разрешается вывести любой.

Примеры
Входные данные
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
Выходные данные
Yes
3 2
4 5
Входные данные
3 5
3 2 1 3
1 3 1 1
3 2 1 4
1 3 2 2
1 3 2 10
Выходные данные
No
Примечание

Andarz Gu в первом тесте из условяи выглядит следующим образом:

Одним из решений является описанное в выходных данных — удалить зачёркнутые на рисунке дороги.

Во втором тесте из условия Andarz Gu выглядит следующим образом: