NOI2024 - D2T3 树形图 - Problem

Problem11177--NOI2024 - D2T3 树形图

11177: NOI2024 - D2T3 树形图

_{[Creator : ]}

Time Limit : 6.000 sec Memory Limit : 512 MiB

Submit Solved: 1 Submit Num: 1 Statistics ShowOff!

Description

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

Input

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

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

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

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

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

Output

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

Constraints

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

Sample 1 Input

Sample 1 Output

3233
2211

样例 $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$ 均为二类点。

Sample 2 Input

Sample 2 Output

3333332333333232333323233333233233333322323333333233332333333333323333333333233333333322332333223233233333233333333333333333223322323333332333333332333323333333333322333323333333323323333333323333333333333333333333333333333233333333323323333332333333333333333233333333333333333333233333323333333333233333333333333323333323233333333333333333333333322333333333333232333233333333332232232233333333333333333333333333333233323232333333332233333323333333333333333333333233332333333233323333332333333333333333233233333333333333333323332332333233333333323333323333333333323333333333333333333333333333223233332332332332333333333333333333333323323333233333323233232333333333233333333333333333332333333333333323333333333332333323333333333333333333323333333333333333333333333333233333233333333333323333322333233332333333233322333333332333333333333333333333233333333322333323323333233333333333333333333233333332233333333333332332333233323333323233333333332233333333333333223333333232333333332332332333233333333233
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
3332332333333323332333333333323333333333333333333333333332233233333333333233233333333332333333333333333333333332333333333233333333333333333333333333323333333333333333233332333333333333333332333333333323333333323332333333333323333333333333233333333333332333333333233333233323223232333233333333333333332333233333333333332322333333333333333323333333332333333333333333333333333333333333233323333323322323323233332233333323333333333233332333333333333323333333332332233233333333333333333333333333333333333333333333333333333333333333333333233333333333333333322322333323332333333233333333333333333323333333333333333333332333332323333333333233333333332333333333333332233333333333333333333333333233333333333332332333333333333333333333333333233332233333333323333233323333333332322333333333333333332333233323332333323333333333333333323333333333333333333333333333323333333333333333323323333333323333333333333333323333333333332323332333332333322323333333333333333333333333333333332333333323233333333332323333333333
3333333232333233333333333333233333332333233333333333333333333333332233323333333233332333333323332333333333333333333333333233323333333333333333233333333323333333233333333333323333333333333332333333333323332323333332332333333323333333333333332223333333333333333333333333233333333333333333333332332233333233333333333333323333333333323233333333222333333333333333333332333333333323333333233333332233323323333333333333333333333332323323333333333333322333333333333332233333333323333333333323333332333233323333333333333323333333232333323223333333323232333333333233333333323322333333323333333323333233333333232332323333333333323333332323333332332333323333332332333332233333333333333332223333333333333333333333333233323222333333333333333333223333332333333333333233333332233233333232333233323332323333323333333333332323333333333333333333223332333333333333332333333333333333323223233333322333332332333333333333333333232333333333323333233323323332233333322333232333333333333333333333333333333333333323333322233333
3232233332323332323332233222322323232233232323332223333233323333332323223333332333333332322333332322323333323323332333233233322333223322332332333233232232323332232233333323233233222333333333333223333333232322332333223333333333232332233332323323332332323323333333322332323333222323322333333232332333233233232333332323332323222332333333233322232323323232333333323333233222333332332233233233323333333323333232233332232322323233232333323333233232333322333333323323233332322233222323323322223232322223333333222332322322223223333233233332333232333222333223332232323333232233223232332333222233233332333333323332333223233232222332333333332233332333332332223233323333232233332232222223322322333323332322232323333322233323333333333233232332333333333232332322233332322333332332233333233333332232332333332233323333333323333332322333333323323233332333323332233332232333233233232222323223323333332333332333233333223333333333323333323333233333333223322233323333333223232333332332333223322332332333332332323222333332
3333323232233232333333222223223323233333332223323223322332233222332332232333333333233333232333222233323323333323333333332332333323232323322333233333222332333333333333332233232333233333233233223322223323223333333333333233223323323333333223233322333323323233233323233232322322233233333333322333232333323333333333322233333223233323333333333233333232332223333323333332233333332333333233333333323323233333323333322333323333333233333233333333332333233233323333332333323333333333333223233323333322223323333333232332333222323322333332333332333223333333232233333323233323223233333233323333323332333323233233333222333233333332333333332323233333323332233222233333222322233333333323332333333232332232333233332332322333333332333333233332323322223333322333223332322333332322232232332233222333233332332322332232233232333333323323332333332233222333333332233333232233333323332233333232323222323323323333322323333232322323223223332232232333332332322333333323333232223233332332333233332322332322222332333223323323332322
3333332333332333323333323333323232333333333333233333333333233333333333333333323333233332333323333333222333333233323323333233332333332333332333333233333323333332333333332332333333233233333322333333333333333333333233333333233332332332333332333323323333332333333333333333333333333332332333233333333223333332333333332332333333333333333333333333332333233323233323333333333332333323233333332333333333333223223233323333323333323323323333333333333333233333333333333333333233333333332233333333333333233333332333333333333333333333332232333333333333323332333323332333333233333333332333333323333323333333233333332332323333333333333233333333333333323333233333332333323323333323333333333333332233333233333322333333333333333332333333333333333333333333333333333323333333333333233333333322232333332323332323223333333333333233333333332333332332333333333233233333333333333333333333333333333323333333233333333332333333333333322233333322333333333333323333333333233333333333333233332333333332333333333332323222332333333323
3223333333323333333233332332232323333333232333323333332333333333333322333233332333223232332333323333323333232333333332333223333333233233333233233223333332333233323333333333323323322332333332233233333322333333333233332333233232323333232333333333223322323332323333323323232333332223322223333233323332233233333323233333333233323323333333232222323333333323233333333233332323333333333333333333233333332223233232333333232333333333323323333323233333233333333332222232323233233333333233322332233333333333233323233223333333333332333333233233333333333233232333323332323333323333233323333333333232333333333333333333233333333333333223333233333323333332332333233233223332333233233332323233333332223333333333322233233333332333233333332233332333332323333333323332233233333323233233332233333233333333322233223333232233233323322333323332323333333323333333223223333223332332332333322333333333333333332333232322333232233333322232223233323333333223233232233323233333333233333323333332223233323333333333232233232233332323
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

11177: NOI2024 - D2T3 树形图

Description

Input

Output

Constraints

Sample 1 Input Copy

Sample 1 Output Copy

Sample 2 Input Copy

Sample 2 Output Copy

Source/Category

Sample 1 Input

Sample 1 Output

Sample 2 Input

Sample 2 Output