| Codeforces Round 326 (Div. 1) |
|---|
| Закончено |
Duff — одна из глав мафии в своей стране Andarz Gu. В Andarz Gu n городов (пронумерованных от 1 до n), соединенных m двусторонними дорогами (пронумерованными от 1 до m).
У каждой дороги есть два специальных параметра — время её разрушения и цвет. i-я дорога соединяет города vi и ui, её цвет — ci, а время разрушения — ti.
Мафия хочет разрушить паросочетание в Andarz Gu. Паросочетание — это подмножество дорог, такое, что никакие две дороги в этом подмножестве не имеют один и тот же город в качестве конца. Дороги можно разрушать параллельно, то есть, время полного разрушения набора дорог определяется как максимум среди времен разрушения всех дорог в наборе.
Имеются два условия:
- Оставшиеся дороги образуют в правильную раскраску.
- Время разрушения этого паросочетания как можно меньше.
После разрушения паросочетания оставшиеся дороги образуют правльную раскраску тогда и только тогда, когда никакие две дороги одного и того же цвета не имеют один и тот же город в качестве конца. Иными словами, для каждого из оставшихся цветов рёбра с этим цветом должны формировать паросочетание.
У мафии нет программиста в штате. Поэтому 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 выглядит следующим образом:
