3041

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <utility>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ull unsigned ll
#define ll long long
#define ull unsigned ll

#define E 2.718281828
#define PI 3.14159265358979323846264338328

// at least 2 nodes, src node != dst node
class max_flow {
public:
	max_flow(int node_cnt) {
		this->node_cnt = node_cnt;
		child = new int*[node_cnt];
		for (int i = 0; i < node_cnt; i++)
			child[i] = new int[node_cnt];
		child_cnt = new int[node_cnt];
		for(int i = 0; i < node_cnt; i++)
			child_cnt[i] = 0;
		cap = new int*[node_cnt];
		for (int i = 0; i < node_cnt; i++)
			cap[i] = new int[node_cnt];
		flow = new int*[node_cnt];
		for (int i = 0; i < node_cnt; i++)
			flow[i] = new int[node_cnt];
		ap = new int[node_cnt];
		bfs_q = new int[node_cnt];
		flag = new bool[node_cnt];
		parent = new int[node_cnt];
		max_flow_res = 0;
	}
	~max_flow() {
		for (int i = 0; i < node_cnt; i++)
			delete[] child[i];
		delete[] child;
		delete[] child_cnt;
		for (int i = 0; i < node_cnt; i++)
			delete[] cap[i];
		delete[] cap;
		for (int i = 0; i < node_cnt; i++)
			delete[] flow[i];
		delete[] flow;
		delete[] ap;
		delete[] bfs_q;
		delete[] flag;
		delete[] parent;
	}
	void set_src(int id) {
		src_id = id;
	}
	void set_dst(int id) {
		dst_id = id; 
	}
	// cannot add same edge more than once
	// bi-direction edge, a->b and b->a are considered as the same, and thus only one can be added
	void add_edge(int id, int id2) {
		child[id][child_cnt[id]++] = id2;
		child[id2][child_cnt[id2]++] = id;
		cap[id][id2] = cap[id2][id] = 0;
		flow[id][id2] = flow[id2][id] = 0;
	}
	// can only be called after add_edge
	void set_cap(int id, int id2, int c) {
		cap[id][id2] = c;
	}
	void clear_flow() {
		max_flow_res = 0;
		for (int id = 0; id < node_cnt; id++)
			for (int i = 0; i < child_cnt[id]; i++) {
				int id2 = child[id][i];
				flow[id][id2] = 0;
			}
	}
	void run() {
		while (get_ap()) {
			int min_rsd = get_ap_flow();
			update_ap_flow(min_rsd);
		}
	}
	int get_max_flow() {
		return max_flow_res;
	}
	bool get_ap() {
		int bfs_q_len = 0;
		for (int i = 0; i < node_cnt; i++)
			flag[i] = false;
		bfs_q[bfs_q_len++] = src_id;
		flag[src_id] = true;
		bool found = false;
		int front = 0;
		while (front < bfs_q_len) {
			int id = bfs_q[front++];
			for (int i = 0; i < child_cnt[id]; i++) {
				int id2 = child[id][i];
				if (cap[id][id2] - flow[id][id2] > 0 && !flag[id2]) {
					bfs_q[bfs_q_len++] = id2;
					flag[id2] = true;
					parent[id2] = id;
					if (id2 == dst_id) {
						found = true;
						break;
					}
				}
			}
			if (found)
				break;
		}
		if (!found)
			return false;
		ap_len = 0;
		int id = dst_id;
		while (id != src_id) {
			ap[ap_len++] = id;
			id = parent[id];
		}
		ap[ap_len++] = src_id;
		return true;
	}
	int get_ap_flow() {
		int id = ap[ap_len - 1], id2 = ap[ap_len - 2];
		int min_rsd = cap[id][id2] - flow[id][id2];
		for (int i = ap_len - 2; i >= 1; i--) {
			id = ap[i], id2 = ap[i - 1];
			int tmp = cap[id][id2] - flow[id][id2];
			if (tmp < min_rsd)
				min_rsd = tmp;
		}
		return min_rsd;
	}
	void update_ap_flow(int f) {
		for (int i = ap_len - 1; i >= 1; i--) {
			int id = ap[i], id2 = ap[i - 1];
			flow[id][id2] += f;
			flow[id2][id] -= f;
		}
		max_flow_res += f;
	}
	void print() {
		for (int id = 0; id < node_cnt; id++)
			for (int i = 0; i < child_cnt[id]; i++) {
				int id2 = child[id][i];
				if (cap[id][id2] > 0)
					std::cout << id << " -> " << id2 << ": " << flow[id][id2] << "/" << cap[id][id2] << std::endl;
			}
	}
	int max_flow_res;
	// id is compressed from 0
	int node_cnt;
	int src_id, dst_id;
	int** child;
	int* child_cnt;
	int** cap;
	int** flow;

	int* ap;
	int ap_len;
	int* bfs_q;
	bool* flag;
	int* parent;
};

int n, k;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	max_flow mf(2 * n + 2);
	mf.set_src(0);
	mf.set_dst(2 * n + 1);
	for (int i = 1; i <= n; i++) {
		mf.add_edge(0, i);
		mf.set_cap(0, i, 1);
	}
	for (int i = n + 1; i <= 2 * n; i++) {
		mf.add_edge(i, 2 * n + 1);
		mf.set_cap(i, 2 * n + 1, 1);
	}
	while (k--) {
		int r, c;
		cin >> r >> c;
		mf.add_edge(r, n + c);
		mf.set_cap(r, n + c, 1);
	}
	mf.run();
	cout << mf.get_max_flow() << endl;
	return 0;
}