사다리 조작

사다리 게임은 세로선 $N$개와 가로선 $M$개로 이루어진다. 인접한 두 세로선 사이에는 가로선을 놓을 수 있고, 가로선을 놓을 수 있는 위치는 세로선마다 $H$개씩 있으며 모든 세로선에서 그 위치가 같다. 아래 그림은 $N = 5$, $H = 6$이면서 가로선이 하나도 없는 경우이다.

초록선은 세로선이고, 초록선과 점선이 만나는 점이 가로선을 놓을 수 있는 자리이다. 가로선은 인접한 두 세로선을 이어야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

이 그림에는 가로선이 5개 있다. 가로선은 그림처럼 인접한 두 세로선을 잇고, 가로선을 놓을 수 있는 자리끼리 이어야 한다.

사다리 게임은 세로선마다 따로 진행하고, 세로선의 맨 위에서 아래로 내려간다. 내려가다가 가로선을 만나면 그 가로선을 타고 옆 세로선으로 옮긴 다음, 옮긴 세로선에서 다시 아래로 내려간다.

이 그림에서는 1번이 3번으로, 2번이 2번으로, 3번이 5번으로, 4번이 1번으로, 5번이 4번으로 도착한다. 아래 두 그림은 1번과 2번이 어떻게 이동하는지 보여준다.

1번 세로선	2번 세로선

사다리에 가로선을 더 놓아서 게임의 결과를 조작하려고 한다. $i$번 세로선에서 출발하면 $i$번에 도착해야 한다. 그렇게 만들려면 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 세로선의 개수 $N$, 가로선의 개수 $M$, 세로선마다 가로선을 놓을 수 있는 위치의 개수 $H$가 주어진다. ($2 \le N \le 10$, $1 \le H \le 30$, $0 \le M \le (N-1) \times H$)

둘째 줄부터 $M$개의 줄에 가로선의 정보가 한 줄에 하나씩 주어진다. 가로선의 정보는 두 정수 $a$와 $b$로 나타낸다. ($1 \le a \le H$, $1 \le b \le N-1$) $b$번 세로선과 $b+1$번 세로선을 $a$번 점선 위치에서 이었다는 뜻이다.

맨 위에 있는 점선이 1번이고, 아래로 내려갈 때마다 번호가 1씩 커진다. 세로선은 맨 왼쪽이 1번이고, 오른쪽으로 갈 때마다 번호가 1씩 커진다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

$i$번 세로선의 결과가 $i$번이 나오도록 사다리 게임을 조작할 때, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 답이 3보다 크면 -1을 출력한다. 불가능한 경우에도 -1을 출력한다.