Противоречие в разностях


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Противоречие в разностях

У n величин x₁…xₙ неизвестны значения. Поступают условия вида «a b d»: xₐ − x_b = d. Найдите номер первого условия, которое противоречит предыдущим (то есть после него набор условий не имеет решения). Если противоречий нет — выведите 0.

Ввод. В первой строке n и m. В следующих m строках условия a b d (a ≠ b, |d| ≤ 10⁹). 2 ≤ n ≤ 100000, 1 ≤ m ≤ 100000.

Вывод. Номер условия или 0.

Примеры

Ввод 1

3 3
1 2 5
2 3 2
1 3 8

Вывод 1

3

Ввод 2

3 3
1 2 5
2 3 2
1 3 7

Вывод 2

0

Комментарии

Еще нет ни одного комментария.