题目描述

给定一个 $n$ 个点 $m$ 条边的简单有向图 $G$，顶点从 $1$ 到 $n$ 编号。其中简单有向图的定义为不存在重边与自环的有向图。

定义顶点 $r$ 是有向图 $G$ 的根当且仅当对于 $1 \leq k \leq n$，顶点 $r$ 到顶点 $k$ 存在恰好一条有向简单路径，其中简单路径的定义为不经过重复点的路径。

定义每个点的种类如下：

• 若顶点 $r$ 是图 $G$ 的根，则称顶点 $r$ 为图 $G$ 的一类点。
• 若顶点 $r$ 不是图 $G$ 的一类点，且存在一种删边的方案，使得图 $G$ 在删去若干条边后得到的图 $G'$ 满足：所有图 $G$ 中的一类点都是 $G'$ 的根，且顶点 $r$ 也是图 $G'$ 的根，则称顶点 $r$ 为图 $G$ 的二类点。
• 若顶点 $r$ 不满足上述条件，则称顶点 $r$ 为图 $G$ 的三类点。

根据上述定义，图 $G$ 的每个点都恰好属于一类点、二类点、三类点之一。你需要判断点 $1 \sim n$ 分别属于这三个种类中的哪一种。

输入格式

从文件 graphee.in 中读入数据。

本题有多组测试数据。

输入的第一行包含一个非负整数 $c$，表示测试点编号。$c = 0$ 表示该测试点为样例。

输入的第二行包含一个正整数 $t$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含两个正整数 $n, m$，分别表示有向图的点数和边数。

接下来 $m$ 行，每行包含两个正整数 $u, v$，表示一条从 $u$ 到 $v$ 的有向边。保证 $1 \leq u, v \leq n$，且给定的有向图 $G$ 不存在重边与自环。

输出格式

输出到文件 graphee.out 中。

对于每组数据，输出一行包含一个长度恰好为 $n$ 的字符串 $s$ 表示每个点的种类。其中 $s_i = 1$ 表示点 $i$ 为一类点，$s_i = 2$ 表示点 $i$ 为二类点，$s_i = 3$ 表示点 $i$ 为三类点。

0
2
4 7
2 1
4 1
1 4
2 3
3 4
2 4
4 3
4 5
1 2
2 3
2 4
3 1
4 3

3233
2211

样例 1 解释

样例 1 共包含两组测试数据。

对于第一组测试数据，输入的图如下：

由于 $1, 3, 4$ 均不存在到达 $2$ 的路径，因此 $1, 3, 4$ 均为三类点。由于 $2$ 到 $1$ 的有向简单路径共有三条：$2 \to 1$，$2 \to 4 \to 1$，$2 \to 3 \to 4 \to 1$，因此 $2$ 不是一类点。删去边 $1 \to 4$，$4 \to 1$，$3 \to 4$，$4 \to 3$ 后，$2$ 到 $1, 3, 4$ 的有向简单路径均唯一，因此 $2$ 是图 $G'$ 的根，即 $2$ 是二类点。

对于第二组测试数据，输入的图如下：

容易发现 $3, 4$ 均为一类点。删去边 $2 \to 3$ 后，每个点到其他所有点的有向简单路径均唯一，因此 $1, 2$ 均为二类点。

样例 2

见选手目录下的 graphee/graphee2.in 与 graphee/graphee2.ans。

这个样例满足测试点 $2$ 的约束条件。

样例 3

见选手目录下的 graphee/graphee3.in 与 graphee/graphee3.ans。

这个样例满足测试点 $3, 4$ 的约束条件。

样例 4

见选手目录下的 graphee/graphee4.in 与 graphee/graphee4.ans。

这个样例满足测试点 $5, 6$ 的约束条件。

样例 5

见选手目录下的 graphee/graphee5.in 与 graphee/graphee5.ans。

这个样例满足测试点 $8, 9$ 的约束条件。

样例 6

见选手目录下的 graphee/graphee2.in 与 graphee/graphee2.ans。

这个样例满足测试点 $14, 15$ 的约束条件。

数据范围

对于所有测试数据保证：$1 \leq t \leq 10$，$2 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$，且图 $G$ 不存在重边与自环。

测试点编号	$t \leq$	$n \leq$	$m \leq$	特殊性质
$1$	$3$	$10$	$20$	无
$2$	$10$	$10^3$	$2, 000$	A
$3, 4$				B
$5, 6$				无
$7$		$10^5$	$2 \times 10^5$	A
$8, 9$				BC
$10 \sim 13$				B
$14, 15$				C
$16 \sim 20$				无

特殊性质 A：保证不存在一类点。

特殊性质 B：保证不存在二类点。

特殊性质 C：保证编号为 $1$ 的点为图 $G$ 的一类点。