gistfile1.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MAX 10010
using namespace std;

int Z, n1, n2, m, result, size;
bool visited[MAX];
int top[MAX], bottom[MAX];
vector<int> graph[MAX];

void load_data_and_cleaning();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
	scanf("%d", &Z);
	while(Z--) {
	  	load_data_and_cleaning();
	  	calculate();
	 	print_data();
	}
 	return 0;
}

void load_data_and_cleaning() {
	scanf("%d %d %d", &n1, &n2, &m);
	int tmp1, tmp2;
	
	size = result = 0;
	for(size_t i = 0; i <= max(n1, n2); ++i) {
		top[i] = bottom[i] = 0;
		visited[i] = false;	
	}
	
	for(size_t i = 1; i <= m; ++i) {
		scanf("%d %d", &tmp1, &tmp2);
		graph[tmp1].push_back(tmp2);
	}	
}

bool DFS(int u) {
	if (visited[u]) return false;
	visited[u] = true;
	
	for(int i = 0; i < graph[u].size(); ++i) {
		if (!top[graph[u][i]] || (graph[u][i] != bottom[u] && DFS(top[graph[u][i]]))) {
			bottom[u] = graph[u][i];
			top[graph[u][i]] = u;
			return true;
		}
	}
	return false;
}

int turbo_phase() {
	result = 0;
	for(int i = 1; i <= n1; ++i)
		if (!bottom[i] && !visited[i] && DFS(i)) result++;
		
	return result;
}

void calculate() {
	while(turbo_phase()) {
		size += result;
		for(size_t i = 0; i <= max(n1, n2); ++i) visited[i] = false;
	}
	
	for(size_t i = 0; i <= n1; ++i)
		graph[i].clear();
}

void print_data() {
	printf("%d\n", size);
}