Laser Mirrors

Farmer John's cows have a powerful laser, but it is fixed at its delivery location. They want to direct the beam to the barn using mirrors mounted on fence posts. The laser and barn lie at distinct points on a 2D plane. The cows can initially point the laser horizontally or vertically (i.e. aligned with the x‐ or y–axis). They may install a mirror on any fence post (if they wish) to turn the beam 90° (from horizontal to vertical, or vice versa). If no mirror is mounted at a fence post, the beam passes over it without changing direction.

You are given the coordinates of the laser, the barn, and N fence posts. Compute the minimum number of mirrors required in order to redirect the laser beam so that it eventually reaches the barn.

Note: The fence posts, the laser, and the barn all lie at distinct coordinates. Moreover, if the laser and barn are already aligned (i.e. they share the same x-coordinate or the same y-coordinate) then no mirrors are needed.

Mathematical formulation:

Let the laser be at point \((x_L,y_L)\) and the barn at \((x_B,y_B)\). There are N fence posts located at \((x_i,y_i)\) for \(i=1,2,\ldots,N\). We want to find the minimal \(M\) such that a path exists from \((x_L,y_L)\) to \((x_B,y_B)\) consisting of line segments that are either horizontal or vertical, and where the change of direction (from horizontal to vertical or vice versa) is allowed only at one of the fence post coordinates. Formally, if the beam changes direction at a fence post then a mirror is used. Otherwise, the beam continues in its current direction.

All formulas are in \(\LaTeX\) style.

inputFormat

The first line contains five integers: x_L y_L x_B y_B N where \(x_L, y_L\) are the coordinates of the laser, \(x_B, y_B\) are the coordinates of the barn, and \(1\le N\le 100{,}000\) is the number of fence posts.

The next N lines each contain two integers: x y, the coordinates of a fence post. All coordinates are distinct, and none of the fence posts share the same coordinates as the laser or barn.

outputFormat

Output a single integer indicating the minimum number of mirrors needed to direct the laser beam from the laser to the barn. If the barn is unreachable, output -1.

sample

0 0 10 0 0

0