Противоречие в разностях
Отправить решение
Решать в редакторе
Сложность:
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
Комментарии