#include<iostream>
using namespace std;
int n, m, ans;
bool e[10005][10005];
void aaa(int now, int sum){
	if(now == m){
		ans = max(ans, sum);
		return;
	}
	aaa(now + 1, sum);
	for(int i = m + 1; i <= n; i ++){
		if(e[now][i]){
			e[now][i] = false;
			aaa(now + 1, sum + 1);
			e[now][i] = true;
		}
	}
}
int main(){
	freopen("tongzhuo.in", "r", stdin);
	freopen("tongzhuo.out", "w", stdout);
	cin >> n >> m;
	int x, y;
	while(cin >> x){
		cin >> y;
		e[x][y] = true;
	}
	aaa(1, 0);
	for(int i = m + 1; i <= n; i ++){
		if(e[1][i]){
			e[1][i] = false;
			aaa(1, 1);
			e[1][i] = true;
		}
	}
	cout << ans;
	return 0;
}