游戏高手
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小 E 和小 P 在玩一个游戏。这个游戏有 n 名角色,角色依次编号为 1-n。每名角色只能被一名玩家选用,由小 E 先手,小 E 和小 P 轮流选择一名未被选用的角色加入己方阵营,直到所有的角色都被选用。
\hspace{15pt}小 E 和小 P 都是游戏高手,他们熟知游戏的角色间共有 m 条克制关系。特别的,这个游戏的策划保证了一名角色最多被一名角色克制,一名角色最多可以克制一名角色。不会有角色被自身克制。
\hspace{15pt}当玩家 A 选择的某名角色能克制玩家 B 选择的某名角色时,玩家 A 的游戏舒适度 +1 ,当玩家 A 选择的某名角色被玩家 B 选择的某名角色克制时,玩家 A 的游戏舒适度 -1
\hspace{15pt}小 E 和小 P 都希望最大化自己的游戏舒适度,为此,他们将选择最有利于自己的角色选择方案,请输出小 E 能达到的最大游戏舒适度。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 t \left(1 \le t \le 1000 \right) 代表数据组数。每组测试数据描述如下:
\hspace{15pt}每组数据第一行输入两个整数 n \left(1 \le n \le 2*10^5 \right),m \left(0 \le m \le n \right) 依次代表角色数量与克制关系数。
\hspace{15pt}接下来 m 行,每行输入两个整数 a,b\left(1 \le a,b \le n ,a \neq b\right) 代表角色 a 克制角色 b。保证一名角色最多被一名角色克制,一名角色最多可以克制一名角色。不会有角色被自身克制。
\hspace{15pt}保证所有测试数据的角色总和数 \sum n \le 2*10^5

输出描述:

\hspace{15pt}对于每一组测试数据,新起一行。输出一个整数代表小 E 能达到的最大游戏舒适度。
示例1

输入

复制
1
4 2
1 2
2 3

输出

复制
1

说明

一种合理的顺序选择方案如下: 
小 E 选择 1,小 P 选择 2,小 E 选择 4,小 P 选择 3
最终,小 E 选择了 [1.4] ,小 P 选择了[2,3]。其中角色 1 克制角色 2 ,小 E 的最大游戏舒适度为 1 ,小 P 的最大游戏舒适度为 -1
可以证明,这对双方来说都采取了最优的选择方式。
示例2

输入

复制
2
4 3
1 2
2 4
4 3
7 5
1 2
2 3
3 4
5 6
6 5

输出

复制
1
0