Конкурс гарбузів
Limits: 2 sec., 256 MiB
Напередодні Гелловіну в селі, назву якого ми не говоримо, проводиться конкурс гарбузів. Кожен мешканець села хоче показати всім, якого великого та страшного гарбуза він виростив.
Для визначення переможця проводяться зважування пар гарбузів. Цим займається весела дітвора. Для кожної пари гарбузів можливі три результати зважування: перший важчий, ніж другий, другий важчий, ніж перший, та ваги гарбузів однакові.
Усі результати зважувань діти записують у протокол. Зараз у протоколі є \(n\) записів, а всього у конкурсі беруть участь \(m\) гарбузів, що пронумеровані від 1 до \(m\).
Через неуважність діти можуть робити помилки під час записування результатів зважувань у протокол.
Вам потрібно визначити, чи є несуперечливою інформація, записана в протоколі. Записи у протоколі вважаються несуперечливими, якщо існують такі дійсні додатні ваги гарбузів, що відповідають їй.
Input
Перший рядок містить два цілих числа \(n\) та \(m\) — кількості записів у протоколі та гарбузів.
Кожен із наступних \(n\) рядків
містить запис у протоколі у вигляді \(x_i\) \(r_i\) \(y_i\), де \(x_i\) та \(y_i\) — номери гарбузів, що зважувалися, а
\(r_i\) — результат зважування
(>
, <
або =
).
Output
Якщо інформація в протоколі є несуперечливою, виведіть
YES
, а інакше — NO
.
Constraints
\(1 \le n, m \le 10^5\),
\(1 \le x_i, y_i \le m\),
\(x_i \ne y_i\),
\(r_i\) є символом >
(якщо \(x_i\) важчий, ніж \(y_i\)), <
(якщо \(y_i\) важчий, ніж \(x_i\)) або =
(якщо їхні ваги
рівні).
Samples
Input (stdin) | Output (stdout) |
---|---|
5 7 1 < 3 2 > 4 7 = 6 6 < 1 7 > 3 | NO |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|