题目描述

小易这一天来到了一个陌生的城市，这个城市可以表示为一张有向图，但可能存在环。小易初始在1号点，同时小易觉得这个城市很有趣，所以他想知道从1号点到其他点的路线个数。

对于每个顶点 v ，输出以下四个值之一：

• 0 ，如果没有从 1 到 v 的路径;
• 1 ，如果只有一条从 1 到 v 的路径;
• 2 ，如果从 1到 v 有多个路径，并且路径数量有限;
• −1 ，如果从 1 到 v 的路径数是无限的。

输入格式

输入的第一行包含一个整数$t（1≤t≤10^4）$，表示输入中的测试案例数量。接下来是$t$个测试案例。每个测试案例前都有一个空行。

每个测试案例的第一行包含两个整数$n$和$m$（$1≤n≤4×10^5，0≤m≤4×10^5$），分别表示图中顶点和边的数量。接下来的m行包含边描述。每行包含两个整数$a_i$和$b_i$（$1\le a_i,b_i \le n$），表示第$i$条边的起点和终点。图中的顶点编号从$1$到$n$。给定的图可能包含环（即$a_i$可能等于$b_i$），但不能包含多重边（即对于$i$不等于$j$的情况，$a_i$不能等于$a_i$且$b_i$不能等于$b_j$）。

所有测试案例中$n$的总和不超过$4×10^5$。同样地，所有测试案例中$m$的总和也不超过$4×10^5$。

输出格式

输出应包含$t$行。第$i$行应该包含第$i$个测试案例的答案：一个由$n$个整数组成的序列，这些整数的取值范围是从$-1$到$2$。

样例数据

5

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

2 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3

1 0 1 2 -1 -1 
1 0
-1 -1 -1 
1 0 0 0 0 
1 1 2 1

样例解释

第一组数据图如下所示

数据规模与约定

输入的附加限制条件：所有测试用例中$n$ 的总和不超过 $4⋅10^5$ 。