#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

int table[101][101] = {0};
int table_size[101] = {0};
int x_value[101] = {0};
int x_size = 0;

int is_match(int depth, int x_index, int n, int used[101]) {
	int i;
	int size;
	int cnt = 0;
	int result = 0;
	int* tused[101];
	for(i=0;i<101;i++) {
		if(used[i] == 1) cnt++;
		if(cnt >= n) return 1;
	}

	if(depth >= n) return 0;
	if(x_index >= x_size) return 0;
	
	// x側が何も選ばない場合
	result |= is_match(depth, x_index+1, n, used);
	size = table_size[x_value[x_index]];
	for(i=0;i<size;i++) {
		if(used[table[x_value[x_index]][i]] == 0) { 
			tused[i] = (int*)malloc(101*sizeof(int));
			memcpy(tused[i], used, sizeof(used));
			tused[i][table[x_index][i]] = 1;
			result |= is_match(depth+1, x_index+1, n, tused[i]);
			free(tused[i]);
		}
	}
	
	return result;
}

int solve(int size) {
	int l = 0;
	int r = size;
	int m = (r + l) / 2;
	int result;
	int old_result = -1;
	int old_m = -1;
	
	if(size == 1) return 1;
	if(size == 0) return 0;
	
	while(1) {
		int used[101];
		memset(used, 0x00, sizeof(used));
		result = is_match(0, 0, m, used);
		if(result > 0 && (old_result == 0 || size == m)) {
			return m;
		} else if(result == 0 && old_result == 1) {
			return old_m;
		} else {
			if(result > 0) {
				m++;
			} else {
				m--;
			}
		}
		
		old_result = result;
		old_m = m;
	}
}

int main(void) {
	int X, Y, E;
	int i,j;
	int x, y;
	int is_found;
	int match_count = 0;
	
	scanf("%d %d %d\n", &X, &Y, &E);
	for(i=0;i<E;i++) {
		scanf("%d %d\n", &x, &y);
		table[x][table_size[x]++] = y;
		
		is_found = 0;
		for(j=0;j<x_size;j++) {
			if(x_value[j] == x) {
				is_found = 1;
				break;
			}
		}
		
		if(is_found==0)	x_value[x_size++] = x;
	}
	
	printf("%d\n", solve(x_size));
	
	return 0;
}