import java.util.Scanner;

public class Main {
	static int N, M, H, ans;
	static int[][][] map;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();
		map = new int[H + 1][N + 1][N + 1];
		ans = 987654321;

		for (int i = 0; i < M; i++) {
			int h = sc.nextInt();
			int n1 = sc.nextInt();
			int n2 = n1 + 1;
			map[h][n1][n2] = 1;
			map[h][n2][n1] = 1;
		}

		builtBridge(1, 1, 0);
		if (ans == 987654321)
			ans = -1;
		System.out.println(ans);
	}

	public static boolean chkArrive(int v) {
		boolean flag = true;
		int start = v;
		for (int j = 1; j < H + 1; j++) { // 층
			for (int k = 1; k < N + 1; k++) { // 가로선
				if (map[j][v][k] == 1) { // 가로선이 있다면
					v = k;
					break;
				}
			}
		}
		if (start != v) {
			flag = false;
		}
		return flag;
	}

	public static void builtBridge(int v, int h, int cnt) {
		if (cnt > 3)
			return;

		int chk = 0;
		for (int i = v; i < N + 1; i++) {
			if (!chkArrive(i)) { // i번 세로선의 결과가 i가 아니라면
				chk = i;
				break;
			}
		}
		if (chk > 0) {
			v = chk;
		} else {
			ans = Math.min(ans, cnt);
			if (ans == 0)
				return;
			return;
		}

		for (int j = v; j < N; j++) { // 맨 마지막줄은 가로선 못만드므로 N까지
			for (int i = h; i < H + 1; i++) {
				if (map[i][j][j + 1] == 0) { // 가로선을 만들 수 있다면
					if (j > 1) {
						if (map[i][j - 1][j] == 1) // 연속된 가로선 있는 경우
							continue;
					}
					map[i][j][j + 1] = 1;
					map[i][j + 1][j] = 1;
					builtBridge(v, i, cnt + 1);
					map[i][j][j + 1] = 0;
					map[i][j + 1][j] = 0;
				}
			}
		}
	}
}