Description

有$N$ 个不同重量的球，重量为$1～N$个单位。对球从$1$到$N$ 进行标记，使得：①没有两个球具有相同的标签；②标签满足几个约束，例如“标签为$a$ 的球比标签为$b$ 的球轻”。

Format

Input

第1行包含测试用例的数量。每个测试用例的第1行都包含两个整数$N （1≤N ≤200）$和$M （0≤M ≤40000）$，分别表示球的数量和约束的数量。后面的$M$ 行，每行都包含两个整数$a$ 和$b$ ，表示标签为$a$ 的球比标签为$b$ 的球轻$（1≤a ,b ≤N ）$。在每个测试用例前都有一个空行。

Output

对于每个测试用例，都单行输出标签$1～N$的球的重量。如果存在多种解决方案，则输出标签为$1$的球的最小重量，然后输出标签为$2$的球的最小重量，以此类推……如果不存在解，则输出$-1$。

Samples

5

4 0

4 1
1 1

4 2
1 2
2 1

4 1
2 1

4 1
3 2

1 2 3 4
-1
-1
2 1 3 4
1 3 2 4

来源

POJ3687