Obelisk

A construction site has $K$ floors, and each floor is an infinitely large grid. Every floor except the bottom one has several holes, and each hole is one cell in size. One cell on the bottom floor is marked X.

A heavy rectangular obelisk of size $1 \times 1 \times M$ stands upright on the top floor. The workers want to stand it upright on the marked cell, with one of its $1 \times 1$ faces on that cell.

The obelisk is too heavy to push or lift. The only way to move it is to tilt it 90 degrees over one of the edges that touch the floor. Each tilt counts as one move.

Diagram 1: rolling an obelisk of size $1 \times 1 \times 2$

To go down one floor, the workers put the obelisk over a hole, and it falls to the floor below. A fall costs no moves, and the obelisk keeps its upright position while it falls.

Diagram 2: an obelisk falling through a hole

The obelisk falls only when every cell it rests on is a hole. No two holes on the same floor share an edge, so an obelisk with $M \ge 2$ never falls while it lies flat. For $M \ge 2$ it falls only when it stands upright on a hole. When $M$ is 1 the obelisk falls the moment it is on a hole. Holes on different floors can be vertically aligned, and then the obelisk falls through several floors in a row until it reaches a cell that is not a hole.

Holes never block the obelisk from rolling. The edges of the obelisk stay aligned with the grid, and at the start the obelisk stands upright on a cell of the top floor that is not a hole.

Find the least number of moves needed to bring the obelisk from its starting position on the top floor to the cell marked X on the bottom floor.

The first line has two integers $K$ and $M$, the number of floors and the height of the obelisk.

The second line has four integers $S_x$, $S_y$, $E_x$, $E_y$. $(S_x, S_y)$ is the cell of the top floor where the obelisk starts, and $(E_x, E_y)$ is the cell marked X on the bottom floor.

Each of the next $K - 1$ lines describes the holes of one floor, from the top floor down to the second floor from the bottom. Each line starts with the number of holes $h$ on that floor, followed by $2h$ space separated integers $x_1$ $y_1$ $x_2$ $y_2$ $\dots$ $x_h$ $y_h$, where $(x_i, y_i)$ is a hole on that floor. Every floor except the bottom floor has at least one hole.

Constraints:

• $2 \le K \le 10$
• $1 \le M \le 5$
• $1 \le S_x, S_y, E_x, E_y \le 30$
• $1 \le h \le 450$, $1 \le x_i, y_i \le 30$
• The holes on one floor are distinct, and no two of them share an edge.
• $(S_x, S_y)$ is not a hole on the top floor.
• Each floor is infinite, so the obelisk may roll outside the coordinate range above.

Print one integer, the least number of moves needed to stand the obelisk upright on the cell marked X. Print -1 if the obelisk cannot be moved there.