给定一个包含 $n$ 个顶点和 $m$ 条边的有向图。图中可能包含自环和重边。 你的任务是判断是否可以通过改变某些边的方向，使得该图成为一个欧拉图。如果可以，你还需要求出改变方向的最少边数。 如果一个有向图存在一条经过每条边恰好一次的有向回路，则称该图为欧拉图。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 1000, 0 \le m \le 5000$)。 接下来的 $m$ 行，每行包含一条边的描述：两个整数 $from$ 和 $to$ ($1 \le from, to \le n$)。 保证所有测试用例中 $n$ 的总和不超过 $1000$。 保证所有测试用例中 $m$ 的总和不超过 $5000$。

输出格式

对于每个测试用例，在单独的一行中输出一个数字：需要改变方向的最少边数；如果无论改变多少条边的方向都无法得到欧拉图，则输出 $-1$。

样例

输入 1

3
3 3
1 2
2 3
1 3
3 2
1 2
2 3
3 3
1 2
2 3
3 1

输出 1

1
-1
0