题目描述

薯条哥最近接到一个游戏设计的工程，其中有 $N$ 个角色（分别编号 $1\sim N$ ）。

在游戏设定中，每个初始角色的战斗力用其等级高低来评价，每个初始角色都会有一个固定的等级。

为了设计一个完善的等级系统，薯条哥为这些初始角色设计了 $M$ 场战斗来测试这些初始角色的强度。

如果战斗的角色等级相等，那么会出现平局；如果不同等级角色之间的战斗，高等级的角色一定会击败低等级角色。

薯条哥想知道应该为这些角色设计多少种等级数量 $ans$ ，如果战斗违反设定或者无法确定，那么就返回$-1$。

输入描述

输入第一行一个整数 $T(1\le T\le 10)$ ，代表测试用例的组数。

接下来 $T$ 组测试数据，对于每一组测试用例，第一行两个整数 $N,M(1\le N\le 10^4,1\le M\le 2\times 10^4)$ ，分别代表角色的数量和战斗的场数。 (可能存在重边)

接下来 $M$ 行，表示角色$A,B(1\le A,B\le N)$的战斗结果，有三种可能:

$1$. $A>B$，表示$A$击败了$B$;

$2$. $A<B$，表示$A$输给了$B$;

$3$. $A=B$，表示$A$和$B$打平;

输出描述

对于每组测试用例，如果战斗结果符合等级设定，输出总共的等级数量 $ans$ ;

否则输出$-1$，表示违反设定或无法确定。

样例

输入

5
4 3
1 < 2
2 < 3
3 = 4
4 3
1 < 2
2 > 3
3 = 4
5 5
1 < 1
1 < 2
2 < 3
3 < 4
4 < 5
7 6
1 < 2
2 < 3
3 < 4
4 < 5
5 < 6
6 = 7
8 6
1 = 2
2 = 4
5 = 4
6 = 7
7 = 8
5 = 6

输出

3
-1
-1
6
-1

样例说明

第一组用例，由$3$和$4$的打平可以得出$3$和$4$处于同一等级，而$3$击败了$2，2$击败了$1$，因此有:${1}<{2}<{3,4}$，共$3$种等级。

第二组用例，$2$击败了$1，2$又击败了$3$,但是无法确定$1$和$3$之间的等级关系，因此无法确定人物之间的等级。

第三组用例，$1$号自己输给自己，违反了相同等级不能分出胜负的设定。

第四组用例，有:${1}<{2}<{3}<{4}>{5}<{6,7}$，共$6$种等级。

第五组用例，$3$没有任何战斗，无法确定其所在等级。