#include<cmath>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

/* POJ 1636 */

const int N = 1005;

int n, m;
bool dp[N][N];
bool vis[2][N];

vector<int> G[2][N];

pair<int, int> dfs(int p, int u) {

	//cout << "DFS " << p << " " << u << endl;

	pair<int, int> res = make_pair(p, p ^ 1);

	vis[p][u] = true;

	for (register int i = 0; i < G[p][u].size(); i++) 
		if (!vis[p ^ 1][G[p][u][i]]) {
			pair<int, int> v = dfs(p ^ 1, G[p][u][i]);
			res.first += v.first, res.second += v.second;
		}

	return res;

}

signed main(void) {

	register int cas;
	scanf("%d", &cas);

	while (cas--) {

		scanf("%d%d", &n, &m);

		memset(dp, 0, sizeof(dp));
		memset(vis, 0, sizeof(vis));

		dp[0][0] = true;

		for (register int i = 0; i <= n; i++)
			G[0][i].clear(), G[1][i].clear();

		for (register int i = 1; i <= m; i++) {

			register int x, y;
			scanf("%d%d", &x, &y);

			G[0][x].push_back(y);
			G[1][y].push_back(x);

		}

		for (register int t = 0; t < 2; t++)
			for (register int i = 1; i <= n; i++)
				if (!vis[t][i]) {

					pair<int, int> tmp = dfs(t, i);

					//printf("tmp %d %d\n", tmp.first, tmp.second);

					for (register int j = n / 2; j >= tmp.first; j--)
						for (register int k = n / 2; k >= tmp.second; k--)
							dp[j][k] |= dp[j - tmp.first][k - tmp.second];

				}

		register int ans = 0;

		for (register int i = 1; i <= n / 2; i++)
			if (dp[i][i])ans = i;

		printf("%d\n", ans);

	}

#ifndef ONLINE_JUDGE
	system("pause");
#endif // !ONLINE_JUDGE


}

/*
 * 注意其中做背包的时候，j和k应当从大向小枚举哦！
 * 千万不要因为专注于“复杂”的DFS而忽视了基础的DP。
 */

• Re:专注于写DFS，竟忽略了背包循环的顺序…… (9) NEIGHTHORN 2016-09-01 23:53:36