H 梳理航道

题目描述

在使用星球特征图确定了自己的位置后，大笨龙驾驶飞船来到猎户座星系，星系中有 $n$ 个星球和 $m$ 条单向航道，这些星球和航道构成一张有向图。每个星球 $i$ 都有一个其他星球的信物 $k_i$，每经过一条航道都需要降落到星球上加油，能降落在某个星球加油当且仅当持有该星球的信物。保证 $k_i$ 构成一个排列。

只要降落在某个星球就自动获得星球内的信物，信物一旦获得便不会被消耗

现在大笨龙拿到了 $i$ 号星球的信物并到了 $i$ 号星球。你需要对每个 $i$ 求出：

1. 有多少星球能被你到达。
2. 有多少星球能被你到达并返回起点 $i$。

请注意：给出的边均是有向边！

输入格式

本题有多组数据。

第一行，一个正整数 $T$，表示数据的组数。对于每组数据：

第一行，两个整数 $n,m$，表示星球数量和航道数量。

第二行，$n$ 个整数 $k_1, k_2, \ldots, k_n$，表示 $i$ 号星球有 $k_i$ 号星球的信物。保证 $k_i$ 构成排列。

接下来 $m$ 行，每行两个整数 $x, y$，表示图上的一条从 $x$ 指向 $y$ 的有向航道。保证不含重边或自环。

输出格式

对于每组数据，输出 $n$ 行，每行两个整数，第 $i$ 行的整数分别表示从 $i$ 号星球出发，能到达的星球数量和能到达并返回起点的星球数量。

输入输出样例

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

4 4
2 1
1 1
1 1
5 5
5 5
3 1
2 1
1 1
2 1
1 1
1 1

说明/提示

【样例解释】

以下是第一组数据的解释：（图中括号内的内容为点上的信物编号）

1. $1$ 能到达的星球集合为 $\{1,2,3,4\}$，$1$ 能到达且能返回 $1$ 的星球集合为 $\{1,2,3,4\}$；
2. $2$ 能到达的星球集合为 $\{2,3\}$，$2$ 能到达且能返回 $2$ 的星球集合为 $\{2\}$；
3. $3$ 能到达的星球集合为 $\{3\}$，$3$ 能到达且能返回 $3$ 的星球集合为 $\{3\}$；
4. $4$ 能到达的星球集合为 $\{4\}$，$4$ 能到达且能返回 $4$ 的星球集合为 $\{4\}$。

这是一个合法的遍历过程：从 $1$ 开始，初始信物为 $2$，到达星球 $2$ 并获得信物 $3$，到达星球 $3$ 并获得信物 $4$，回到星球 $1$，到达星球 $4$ 并获得信物 $1$，到达星球 $3$，回到星球 $1$。

【数据范围】

对于 $100\%$ 的数据，满足 $n \ge 3$，$m\ge 0$，$\sum n\le 1.5\times{10}^6$，$\sum m\le 3\times{10}^6$，$1 \le T\le 2\times{10}^4$，$1 \le x, y \le n$，保证图中不含重边或自环。

本题采用捆绑测试且开启子任务依赖！