{"raw_statement":[{"iden":"background","content":"邮箱，一种历史悠久的接信箱子。西方的邮箱以红色为主，东方的邮箱以绿色为主。"},{"iden":"statement","content":"有一张 $n$ 个点和 $m$ 条边构成的**有向**图。每个点内都有一把另一个点的钥匙，$i$ 号点内有 $k_i$ 号点的钥匙。你能进入一个点当且仅当你有该点的钥匙。保证 $k_i$ 构成排列。\n\n只要进入了一个点，就获得了这个点内有的钥匙。一旦获得钥匙就不会被消耗。\n\n现在你拿到了 $i$ 号点的钥匙并到了 $i$ 号点。你需要对每个 $i$ 求出：\n\n1. 有多少点能被你到达。\n2. 有多少点能被你到达并返回起点 $i$。\n\n**请注意：给出的边均是有向边！**"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行，一个正整数 $T$，表示数据的组数。对于每组数据：\n\n第一行，两个整数 $n,m$，表示图的点数和边数。\n\n第二行，$n$ 个整数 $k_1, k_2, \\ldots, k_n$，表示 $i$ 号点内有 $k_i$ 号点的钥匙。保证 $k_i$ 构成排列。\n\n接下来 $m$ 行，每行两个整数 $x, y$，表示图上的一条从 $x$ 指向 $y$ 的有向边。保证不含重边或自环。"},{"iden":"output","content":"对于每组数据，输出 $n$ 行，每行两个整数，第 $i$ 行的整数分别表示从 $i$ 号点出发，能到达的点数和能到达并返回起点的点数。"},{"iden":"note","content":"**【样例解释】**\n\n以下是第一组数据的解释：（图中括号内的内容为点上的钥匙编号）\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/hrserkw2.png)\n\n1. $1$ 能到达的结点集合为 $\\{1,2,3,4\\}$，$1$ 能到达且能返回 $1$ 的结点集合为 $\\{1,2,3,4\\}$；\n2. $2$ 能到达的结点集合为 $\\{2,3\\}$，$2$ 能到达且能返回 $2$ 的结点集合为 $\\{2\\}$；\n3. $3$ 能到达的结点集合为 $\\{3\\}$，$3$ 能到达且能返回 $3$ 的结点集合为 $\\{3\\}$；\n4. $4$ 能到达的结点集合为 $\\{4\\}$，$4$ 能到达且能返回 $4$ 的结点集合为 $\\{4\\}$。\n\n这是一个合法的遍历过程：从 $1$ 开始，初始钥匙为 $2$，到达结点 $2$ 并获得钥匙 $3$，到达结点 $3$ 并获得钥匙 $4$，回到结点 $1$，到达结点 $4$ 并获得钥匙 $1$，到达结点 $3$，回到结点 $1$。\n\n**【数据范围】**\n\n对于 $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$，保证图中不含重边或自环。\n\n**本题采用捆绑测试且开启子任务依赖！**\n\n|子任务|对 $n$ 的约束|对 $m$ 的约束|分值|依赖|\n|-|-|-|-|-|\n|1|$n\\le 6$|$m\\le 12$|$20$|\\ |\n|2|$\\sum n^3\\le {10}^7$|$\\sum m^3\\le 2\\times {10}^7$|$25$|\\ |\n|3|$\\sum n^2\\le {10}^8$|$\\sum m^2\\le {10}^8$|$25$|子任务 1、2|\n|4|||$30$|子任务 1、2、3|"}],"translated_statement":null,"sample_group":[["3\n4 5\n2 3 4 1\n1 2\n2 3\n3 1\n1 4\n4 3\n5 6\n2 3 4 5 1\n1 2\n2 3\n3 4\n4 5\n5 2\n4 1\n3 2\n2 3 1\n1 2\n1 3\n","4 4\n2 1\n1 1\n1 1\n5 5\n5 5\n3 1\n2 1\n1 1\n2 1\n1 1\n1 1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}