You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

为了设计一个完善的等级系统，塔子哥为这些初始角色设计了 $M$ 场战斗来测试这些初始角色的强度。如果战斗的角色等级相等，那么会出现平局；如果不同等级角色之间的战斗，高等级的角色一定会击败低等级角色。

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

输入描述

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

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

接下来 $M$ 行，表示角色A和角色B的战斗结果( $1 \leq A,B \leq 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没有任何战斗，无法确定其所在等级。