P10790 [NOI2024] 树形图

由于评测机性能差异，本题时限翻倍。

给定一个 $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$ 分别属于这三个种类中的哪一种。

**本题有多组测试数据。** 输入的第一行包含一个非负整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。 输入的第二行包含一个正整数 $t$，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： 输入的第一行包含两个正整数 $n,m$，分别表示有向图的点数和边数。 接下来 $m$ 行，每行包含两个正整数 $u,v$，表示一条从 $u$ 到 $v$ 的有向边。保证 $1\leq u,v\leq n$，且给定的有向图 $G$ 不存在重边与自环。

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

**【样例 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$ 均为二类点。 **【数据范围】** 对于所有测试数据保证：$1\leq t\leq 10$，$2\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，且图 $G$ 不存在重边与自环。 ::cute-table{tuack} | 测试点编号 | $t\leq$ | $n\leq$ | $m\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $3$ | $10$ | $20$ | 无 | | $2$ | $10$ | $10^3$ | $2000$ | 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$ 的一类点。