Ladder Manipulation

A ladder game is built from $N$ vertical lines and $M$ horizontal lines. A horizontal line can be placed between two adjacent vertical lines. Every vertical line has $H$ positions that can hold a horizontal line, and those positions are the same on every vertical line. The picture below shows $N = 5$, $H = 6$ with no horizontal line.

The green lines are the vertical lines, and each point where a green line meets a dotted line can hold a horizontal line. A horizontal line must connect two adjacent vertical lines. Two horizontal lines must not be consecutive and must not touch each other. A horizontal line must also lie on a dotted line.

This picture has 5 horizontal lines. Each horizontal line connects two adjacent vertical lines, and it connects positions that can hold a horizontal line.

The ladder game runs separately for each vertical line and moves from the top of that vertical line downward. When the walk meets a horizontal line, it crosses to the neighboring vertical line along that horizontal line and then continues downward on the new vertical line.

In this picture, 1 ends at 3, 2 ends at 2, 3 ends at 5, 4 ends at 1, and 5 ends at 4. The two pictures below show how 1 and 2 move.

Vertical line 1	Vertical line 2

You want to change the outcome of the game by adding horizontal lines to the ladder. A walk that starts at vertical line $i$ must end at vertical line $i$. Write a program that finds the minimum number of horizontal lines you have to add.

The first line contains the number of vertical lines $N$, the number of horizontal lines $M$, and the number of positions $H$ on each vertical line that can hold a horizontal line. ($2 \le N \le 10$, $1 \le H \le 30$, $0 \le M \le (N-1) \times H$)

Each of the next $M$ lines describes one horizontal line with two integers $a$ and $b$. ($1 \le a \le H$, $1 \le b \le N-1$) It means that vertical line $b$ and vertical line $b+1$ are connected at dotted line position $a$.

The topmost dotted line is number 1, and the number grows by 1 for each step down. The leftmost vertical line is number 1, and the number grows by 1 for each step to the right.

No two horizontal lines given in the input are consecutive.

Print the minimum number of horizontal lines you have to add so that a walk starting at vertical line $i$ ends at vertical line $i$. If the answer is greater than 3, print -1. If it is impossible, print -1 as well.