Предположим, у нас есть глобальная переменная $$$v$$$, и мы определили операцию "Compare-and-Set" для нее. Операция проверяет, равна ли переменная $$$a$$$. Если это верно, значение переменной изменяется на $$$b$$$, и операция успешна. В противном случае переменная не изменяется, и операция неудачна. Обозначим эту операцию как $$$\operatorname{CAS}(a,b)$$$.
Представьте, что у вас есть список таких операций $$$\operatorname{CAS}(a_1,b_1), \dots, \operatorname{CAS}(a_n,b_n)$$$. Также у вас есть начальное значение переменной, $$$c$$$, и список желаний $$$w_1, \dots w_n$$$, где $$$w_i$$$ указывает, должна ли операция $$$\operatorname{CAS}(a_i,b_i)$$$ быть успешной. Ваша задача - определить порядок выполнения операций так, чтобы все желания были удовлетворены.
Первая строка содержит два целых числа $$$n$$$ и $$$c$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le c \le 10^9$$$) — количество операций и начальное значение переменной.
Каждая из следующих $$$n$$$ строк содержит три целых числа $$$a_i, b_i, w_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$; $$$0 \le w_i \le 1$$$), обозначающих операцию $$$\operatorname{CAS}(a_i, b_i)$$$, которую вы хотите, чтобы она была успешной, если $$$w_i = 1$$$, и неудачной, если $$$w_i = 0$$$. Операции пронумерованы от $$$1$$$ до $$$n$$$ в порядке ввода.
Если не существует правильного порядка операций, выведите слово "No".
В противном случае выведите слово "Yes" и затем $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots p_n$$$ ($$$1 \le p_i \le n$$$), означающих, что операция $$$p_1$$$ должна быть выполнена первой, затем операция $$$p_2$$$ и так далее. Если существует несколько возможных порядков, выведите любой из них.
4 1 1 2 0 1 2 1 2 3 1 3 4 0
Yes 4 2 1 3
3 1 1 2 1 1 2 1 1 2 0
No
| 2020-2021 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
