| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 5 | 4 | 4 | 80.000% |
В мертвом городе живет $n$ зомби. Они живут в $n$ домах, соединенных $m$ дорогами, причём не обязательно можно дойти от каждого дома до любого другого по дорогам (пока дойдешь от одного дома до другого, уже все конечности отвалятся).
Зомби --- ужасно социальные и при этом ужасно глупые существа. Ввиду своей социальности зомби часто ходят в гости друг к другу, а ввиду глупости не любят строить маршруты для походов в гости. После того, как в прошлый Хэллоуин зомби Чак заблудился и так и не вернулся домой, они решили, что надо поменять планировку города, чтобы перемещения стали проще.
Перед новым Хэллоуином, они просят вас разрушить несколько дорог так, чтобы между каждой парой домов существовало не более одного пути по дорогам. При этом поскольку они остаются социальными, им хочется, чтобы вы разрушили для этого как можно меньше дорог, чтобы как можно больше пар домов все еще были достижимы друг от друга. Кроме того, некоторые дороги настолько полюбились в этом обществе, что их вообще ни в коем случае нельзя ломать.
Помогите им определить, какие дороги следует разрушить, либо скажите что добиться желаемого условия невозможно, не сломав их любимые дороги.
В первой строке ввода через пробел даны целые числа $n$ и $m$ (1ドル \leq n \leq 10^5,ドル 1ドル \leq m \leq 10^5$) --- количество домов и дорог соответственно.
В следующих $m$ строках описаны дороги, по одной на строке. Описание $i$-й дороги состоит из трех целых чисел $u_i,ドル $v_i$ и $t_i$ (1ドル \leq u_i, v_i \leq n$; $u_i \neq v_i$; 0ドル \leq t_i \leq 1$). Это означает, что существует дорога между домами $u_i$ и $v_i,ドル и эту дорогу нельзя разрушать, если $t_i = 1,ドル и можно, если $t_i = 0$.
Гарантируется что между любой парой домов существует не больше одной дороги.
Выведите <<NO>> (без кавычек), если невозможно разрушить дороги так, чтобы удовлетворить потребности зомби.
Иначе в первой строке выведите <<YES>>, а затем целое число $k$ --- количество дорог, которые нужно разрушить. В следующих $k$ строках выведите пары целых чисел $x_i$ и $y_i,ドル разделенные пробелом --- номера домов, дорогу между которыми вы разрушаете.
4 3 1 2 0 2 3 0 1 3 0
YES 1 1 2
4 3 1 2 1 2 3 1 1 3 1
NO