Bug2 Path Length

Navigation problems appear all around us. This problem is about a navigation strategy called the Bug2 algorithm.

Bug algorithms solve the following navigation task. We are given a two-dimensional map that contains obstacles of arbitrary shape, together with a start point and a finish point. An agent initially stands at the start point S, and its goal is to reach the finish point F. The agent knows the coordinates of F and, at any moment, can determine its own coordinates. The agent has only O(1) memory, so it cannot store the map of obstacles. The only information it can gather about the world is whether it is currently touching an obstacle. The agent is able to move along the boundary of an obstacle. Its task is to reach F when that is possible, and otherwise to correctly report that F is unreachable.

The Bug2 algorithm works as follows:

1. Move straight toward F until one of the following happens:

   • F is reached. The algorithm stops.
   • An obstacle is encountered. Go to step 2.

2. Call the current point H. Follow the boundary of the obstacle in the clockwise direction until one of the following happens:

   • F is reached. The algorithm stops.
   • The point H is reached again. Then F is unreachable, and the algorithm stops.
   • A point L is reached that lies on the line SF, satisfies |LF| < |HF|, and from which it is possible to move toward F without immediately re-entering the obstacle. Go to step 1.

One can prove that this algorithm always reaches F in finite time when F is reachable, and otherwise reports unreachability in finite time.

Given a set of polygonal obstacles together with a start point and a finish point, determine the length of the path traced by an agent that follows the Bug2 algorithm.

The first line contains five integers n, xS, yS, xF, yF — the number of obstacles and the coordinates of the start and finish points.

The remaining lines describe the obstacles. Each obstacle description begins with a line containing an integer m (m ≥ 3), the number of vertices of that obstacle. The next m lines each contain two integers xi, yi — the coordinates of the obstacle's vertices, given in clockwise order. Each obstacle is a simple polygon with no self-intersections and no self-tangencies.

Constraints:

• The total number of vertices over all obstacles does not exceed 300000.
• Every coordinate has absolute value at most 10^6.
• Every edge of every obstacle is parallel to a coordinate axis (all obstacles are rectilinear).
• The start and finish points share the same y-coordinate, i.e. the segment SF is horizontal.
• No obstacle vertex lies on the line SF.
• Both the start and the finish point lie strictly outside every obstacle.
• No two obstacles share a common point.
• The finish point F is reachable by the agent.

Under these conditions the path traced by the agent consists only of axis-parallel segments whose endpoints have integer coordinates.

Output a single integer: the total length of the path traced by the agent that follows the Bug2 algorithm.

Because every obstacle is rectilinear and the segment SF is horizontal, every segment of the agent's path is axis-parallel with integer endpoints, so the total length is always an integer. Print that integer exactly, with no decimal point and no trailing zeros.