package bj.gold.l4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;
/**
* @author 은서파
* @since 2020. 7. 30
* @see https://www.acmicpc.net/problem/15684
* @performance 13736 272, 싹수 노란 녀석들 제거: 13700 96
* @category #완탐
* @memo
*/
public class BJ_G4_15684_사다리조작{
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens;
static int C, M, R;
static int [][] ladder;
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
tokens = new StringTokenizer(input.readLine());
C = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
R = Integer.parseInt(tokens.nextToken());
ladder = new int [R+1][C+1];
for(int m=0; m<M; m++) {
tokens = new StringTokenizer(input.readLine());
int a = Integer.parseInt(tokens.nextToken());
int b = Integer.parseInt(tokens.nextToken());
ladder[a][b] = 1; // 가로선의 시작점
ladder[a][b+1] = -1; // 가로선의 맞은 편
}// 입력 처리 완료
// 싹수가 노란 녀석은 버리기
if(getOddCnt() >3) {
System.out.println(-1);
return;
}
// 0~3개까지 가로선을 추가해보면서 게임이 끝나는지 살펴보자.
for(int i=0; i<=3; i++) {
// i 개수만큼 가로선 추가해보기
boolean result = makeLine(1, 1, i, i);
if(result) {
return;
}
}
// 아직 안끝났다면?
System.out.println(-1);
}
/**
* lineCnt 만큼의 선을 그어가보면서 선택이 완료되면 check 호출로 결과 확
* @param sr 출발점 row
* @param sc 출발점 col
* @param toChoose 골라야할 개수
* @param lineCnt 고르기로 한 개수
* @return
*/
private static boolean makeLine(int sr, int sc, int toChoose, int lineCnt) {
if(toChoose==0) {
if(check()) {
System.out.println(lineCnt);
// 정답을 골랐으니 더이상 재귀 돌 필요 없어요~~~
return true;
}
return false;
}
for(int r=sr; r<=R; r++) {
for(int c=sc; c<C; c++) {
if(ladder[r][c]==0 && ladder[r][c+1]==0) {
ladder[r][c]=1;
ladder[r][c+1]=-1;
// 가지치기
if(makeLine(r, c+2 , toChoose-1, lineCnt)) {
return true;
}
ladder[r][c]=0;
ladder[r][c+1]=0;
}
}// row 하나 체크 완료
// row가 변경되면 col은 1부터 시작해야 한다.
sc=1;
}
return false;
}
/**
* 사다리의 모든 컬럼에서 출발했을 때 도착지가 출발점의 세로선과 일치하는지 반환
* @return
*/
private static boolean check() {
for(int c=1; c<=C; c++) {
int nc = c; // 이동하고 있는 컬럼의 좌표
for(int r=1; r<=R; r++) {
// 1이면 오른쪽으로, -1이면 왼쪽으로
if(ladder[r][nc]==1) {
nc++;
}else if(ladder[r][nc]==-1) {
nc--;
}
}// 해당 c에 대한 체크 완료!!
if(c !=nc) {
return false;
}
}
return true;
}
private static int getOddCnt() {
int oddLine = 0;
for(int c=1; c<C; c++) {
int num=0;
for(int r=1; r<=R; r++) {
if(ladder[r][c]==1) {
num++;
}
}
if(num%2==1) {
oddLine++;
}
}
return oddLine;
}
// REMOVE_START
private static String src = "5 6 6\n"
+ "1 1\n"
+ "3 1\n"
+ "5 2\n"
+ "4 3\n"
+ "2 3\n"
+ "1 4";
// REMOVE_END
}