Baekjoon-15684-사다리 조작

N,M,H = map(int,input().split())
vlines = [[] for _ in range(H)]
for _ in range(M):
    a,b = map(int,input().split())
    vlines[a-1].append(b-1)

# 최대 3개까지만 가로선 추가 가능
answer = 4
def dfs(depth, nums, arr, idx):
    global answer
    if depth == H:
        if arr == list(range(N)):
            answer = min(answer, 3-nums)
    else:
        if nums != 0:
            for j in range(idx,N-1):
                if j-1 not in vlines[depth] and j not in vlines[depth] and j+1 not in vlines[depth]:
                    vlines[depth].append(j)
                    dfs(depth, nums-1, arr,j+2)
                    vlines[depth].pop()

        # swap
        new_arr = [i for i in arr]
        for b in vlines[depth]:
            new_arr[b], new_arr[b+1] = arr[b+1], arr[b]
        dfs(depth+1,nums,new_arr,0)

dfs(0,3,list(range(N)),0)
if answer == 4:
    print(-1)
else:
    print(answer)