Сумасшедший город представляет собой плоскость, на которой имеется n бесконечных прямых дорог. Каждая дорога задаётся уравнением aix + biy + ci = 0, где ai и bi не равны нулю одновременно. Дороги разбивают плоскость на связные области, возможно бесконечной площади. Каждую такую область назовем кварталом. Перекрестком будем называть точку пересечения хотя бы двух различных дорог.
Ваш дом расположен в одном из кварталов. Сегодня вам надо добраться до университета, также расположенного в некотором квартале. За один шаг вы можете переместиться из одного квартала в другой, если протяжённость их общей границы ненулевая (в частности это значит, что если кварталы смежны одному перекрёстку, но не имеют общего ненулевого отрезка границы, то перейти из одного в другой за один шаг нельзя).
Определите, какое минимальное количество шагов вам придётся сделать, чтобы оказаться в квартале, содержащем университет. Гарантируется, что ни ваш дом, ни университет не расположены на дороге.
Выходные данные
В единственной строке выведите одно целое число — ответ на задачу.
Примечание
Рисунки к примерам представлены ниже (A — точка, соответствующая дому; B — точка, соответсвующая университету; разными цветами обозначены области, соответствующие разным кварталам):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
-1 -1
2
0 1 0
1 0 0
|
2
|
|
2
|
1 1
-1 -1
3
1 0 0
0 1 0
1 1 -3
|
2
|