描述

为了降低骚乱和越狱的风险，两座相邻且囚犯容量相同的监狱的管理委员会决定在彼此之间重新安排囚犯。他们希望将其中一座监狱的一半囚犯与另一座监狱的一半囚犯进行交换。然而，从囚犯犯罪历史的存档信息中，他们了解到有些囚犯对如果被关在同一所监狱会很危险，这就是为什么他们如今被分开的原因，即对于每对这样的囚犯，一名囚犯在第一所监狱服刑，另一名在第二所监狱服刑。管理委员会一致认为将这些囚犯对分开关押很重要，这使得他们的重新安排任务变得有些棘手。事实上，他们很快发现有时无法实现交换一半囚犯的愿望。每当出现这种情况时，他们不得不满足于尽可能接近一半囚犯的交换。

输入

输入的第一行是一个正整数n，表示接下来的测试场景数量。每个场景的第一行包含两个非负整数m和r，其中1 < m < 200是每所监狱的囚犯数量，r是囚犯之间危险对的数量。接下来的r行，每行包含一对范围在1到m之间的整数xi yi，表示第一所监狱的囚犯xi不能与第二所监狱的囚犯yi关押在同一所监狱。

输出

对于每个测试场景，输出一行包含最大的整数k ≤ m/2，使得可以将第一所监狱的k名囚犯与第二所监狱的k名囚犯进行交换，而不会使任何危险对的两名囚犯在同一所监狱。

输入数据 1

3
101 0
3 3
1 2
1 3
1 1
8 12
1 1
1 2
1 3
1 4
2 5
3 5
4 5
5 5
6 6
7 6
8 7
8 8

输出数据 1

50
0
3

来源

2003年西北欧竞赛