# Appreciation

/*
 * Problem :: 15684 / 사다리 조작
 *
 * Kind :: DFS + Backtracking
 *
 * Insight
 * - 추가해야 하는 가로선 개수의 최솟값을 출력한다
 *   만약, 정답이 3보다 큰 값이면 -1 을 출력한다 / 또, 불가능한 경우에도 -1을 출력한다.
 *   + 사다리를 (0,1,2,3) 개 놓는 경우만 생각하면 된다...?
 *     그럼 다 해볼 수 있나?
 *     # 가능한 가로선의 위치의 개수는 max(M)=270
 *       놓지 않는 경우도 생각하면 271가지의 위치가 가능함
 *       가로선은 최대 3개 놓아야함 => O(271^3)
 *       가로선을 놓았을 때 옳은 결과가 나오는가 확인 => max(N)*max(H)=300
 *       271^3 * 300 = 5.9707533 * 10^9
 *       좀 많은데...?
 *       (물론 위에는 크게크게 잡은 거고
 *        중간에 가로선 하나만 있더라도 그 위치와 양옆의 위치에 가로선을 넣을 수 없어서
 *        max(M)은 많이 줄어들 것 같긴 한데...)
 *
 * - 정직하게 다 해볼 필요 없다
 *   + 사다리를 2개를 놓아서 옳은 결과가 나온다면 거기서 탐색을 끝내고 답을 출력한다
 *     # 그래도 최악의 경우는 3개를 놓는 경우를 다 찾아봐야 할텐데...
 *       -> 뭔가 나름의 최적화가 필요하다 (아니면 다른 방법을 찾던가)
 *
 * - |   |   |
 *   |   |   |
 *   |   |---|
 *   |   |   |
 *   라는 사다리가 있다고 하자
 *   + |---|   |
 *     |   |   |
 *     |   |---|
 *     |   |   |
 *     (1,1) 에 가로선을 놓았을 때 옳은 결과가 나오는지 탐색했다
 *     그렇다면...
 *     # |   |   |
 *       |---|   |
 *       |   |---|
 *       |   |   |
 *       (2,1) 에 가로선을 놓은 결과를 탐색해야 할까?
 *       그렇지 않다, (1,1) 에 가로선을 놓은 결과가 똑같을 것이기 때문이다
 *       그럼...
 *       -> |   |   |
 *          |   |   |
 *          |   |---|
 *          |---|   |
 *          (4,1) 에 가로선을 놓은 결과를 탐색해야 할까?
 *          그렇다. (2,2) 에 가로선이 있기 때문에 결과가 달라질 수 있기 때문이다
 *          즉, (y,x) 위치에 가로선을 놓고 탐색한 후 다음에 탐색할 가로선의 위치는
 *          같은 x 좌표이며 적어도 양 옆에 다른 가로선이 있었던 y 좌표의 바로 다음 y 좌표이다
 *          (그런데 정확한 시간복잡도는 고려해야 되는 경우가 많아서 계산하지 못하겠다... 
 *           최적화를 적용하지 않았을 때는 시간초과가 나고
 *           그렇지 않았을 때는 0ms 로 통과했으니 많이 줄어든다고 치자 ㅠㅠ)
 *
 * Point
 * - 솔직히 말하자면
 *   이전에 짰던 나의 코드는 1000ms 넘게 나오는데 <= 최적화 사용 X, 구현이 살짝 다름
 *   다른 사람의 코드는 0ms 가 있어서 그런 분들의 코드를 참고했다
 *   + 역시 똑똑한 사람들은 많고 나는 아직 많이 부족하다 ㅠㅠ
 *     # 저런 최적화를 어떻게 생각하셨을까...
 *
 * - 이전에 놓았던 사다리의 위치를 기억해서
 *   그 다음부터 사다리를 놓는 최적화도 가능하다
 *   + 인자의 개수도 많아지고 다음에 놓을 위치를 찾기위한 로직도 필요하고...
 *     위의 최적화도 충분히 강력하니까... (죄송합니다, 귀찮았습니다)
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M, H;
bool isBridge[30+1][10+1];

// Set up : Functions Declaration
int arrive(int no);
bool isOk();
bool f(int cnt);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> M >> H;
    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        isBridge[a][b] = true;
    }

    // Process
    // Control : Output
    for (int i=0; i<=3; i++) {
        if (f(i)) { /* 사다리를 i개 놓았을 때 옳은 결과가 나온다면 */
            cout << i << endl; /* i 를 출력하고 */
            exit(0); /* 바로 종료 */
        }
    } /* 사다리를 [0,3] 개 놓는게 불가능 했거나 놓았더라도 모두 옳은 결과가 나오지 않았다면 */
    cout << -1 << endl; /* -1 을 출력하고 종료 */
}

// Helper Functions
int arrive(int no)
/* no 번 세로선의 결과를 반환 */
{
    for (int i=1; i<=H; i++) {
        if (isBridge[i][no]) { /* (i,no) 에 가로선이 있다면 */
            no++; /* 오른쪽으로 한칸 이동 */
        } else if (isBridge[i][no-1]) { /* (i,no-1) 에 가로선이 있다면 */
            no--; /* 왼쪽으로 한칸 이동 */
        }
    } return no;
}

bool isOk()
/* 모든 세로선의 결과가 자신의 번호와 같은 옳은 결과가 나오면 true 를 반환
 * 그 외 false 를 반환 */
{
    for (int i=1; i<=N; i++) {
        if (i != arrive(i)) return false;
    } return true;
}

bool f(int cnt)
/* cnt 개의 사다리를 추가로 놓을 때, 옳은 결과가 나오면 true 를 반환
 * 그 외 false 를 반환 */
{
    /* 사다리를 다 놓았을 때 */
    if (cnt == 0) {
        /* 옳은 결과의 여부를 반환 */
        return isOk();
    }

    for (int j=1; j<=N-1; j++) {
        for (int i=1; i<=H; i++) {
            /* (i,j) 에 가로선을 놓고 싶은 경우,
             * (i,j-1) (i,j) (i,j+1) 에 가로선이 없어야 한다 */
            if (isBridge[i][j-1] || isBridge[i][j] || isBridge[i][j+1]) continue;

            isBridge[i][j] = true; /* (i,j) 에 가로선을 놓음 */
            /* (i,j) 에 가로선을 넣은 상태에서,
            * (cnt-1) 개의 가로선을 추가로 넣었을 때 옳은 결과가 나왔다면
            * 바로 true 를 반환하며 함수 종료 */
            if (f(cnt-1)) return true;
            /* (i,j) 에 가로선을 뺌
             * (i,j) 에 가로선을 넣어선 옳은 결과를 얻을 수 없음 */
            isBridge[i][j] = false;

            /* 최적화 - Insight 부분의 설명을 참고 */
            while (not(isBridge[i][j-1]) && not(isBridge[i][j+1])) i++;
        }
    }

    /* 다 해봤는데 불가능 하면 false 를 반환 */
    return false;
}