Дом улыбок создан, чтобы повышать настроение. В нем есть n комнат. Некоторые из комнат соединены дверьми. Про каждые две комнаты (с номерами i и j), которые соединены дверью, Петя знает величину cij — на сколько изменяется у него настроение при переходе из комнаты с номером i в комнату с номером j.
Петя задумался: может ли он поднять себе настроение до бесконечности, двигаясь по какому-нибудь циклу? А если может, то какое минимальное количество комнат ему надо будет проходить за один период цикла?
Выходные данные
Выведите минимальное количество комнат, которое необходимо проходить за один проход по циклу, бесконечно повышающему настроение, или число 0, если такого цикла не существует.
Примечание
Напомним, что циклом называется такая последовательность комнат a1, a2, ..., ak, что a1 соединена с a2, a2 соединена с a3, ..., ak - 1 соединена с ak, ak соединена с a1. Некоторые элементы последовательности могут совпадать, то есть цикл не обязательно должен быть простым. Количеством комнат в цикле считается k, длина последовательности. Заметим, что минимальная возможная длина равна двум.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3
|
4
|