Коровы Фермера Джона любят производить лазерные шоу.
Для своего последнего шоу, они купили огромный мощный лазер - такой большой, что они не смогли перместить его легко из того места, где он был приобретен. Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться как точки на плоскости - карте фермы ФД. В панах коров направить лазер так, чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал, чтобы направить луч в амбар.
На этой ферме есть n точек изгороди, расположенных в различных точках на плоскости, (и отличающихся также от точек лазера и амбара), на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в вертикальный и наоборот.
Вычислите минимально возможное количество зеркал, которое необходимо коровам, чтобы пернаправить лазер в амбар.
Первая строка содержит 5 целых чисел n (1 ≤ n ≤ 10^5
), x[l]
, y[l]
, x[b]
, y[b]
, где (x[l]
, y[l]
) - это размещение лазера, (x[b]
, y[b]
) - размещение амбара. Все координаты между 0 и 10^9
.
Каждая из следующих n строк содержит x и y - координаты точек изгороди - целые числа в интервале 0 .. 10^9
.
Выведите минимальное колчиество зеркал, которое необходимо чтобы перенаправить лазер в амбар, или -1, если это невозможно сделать.