9509 - 树形图

给定一个 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 不存在重边与自环。

NOI