P9150 Mailbox Problem.

A mailbox is a long-standing box for receiving letters. In the West, mailboxes are mainly red, while in the East, mailboxes are mainly green.

You are given a **directed** graph with $n$ vertices and $m$ edges. Each vertex contains a key to another vertex: vertex $i$ contains the key to vertex $k_i$. You can enter a vertex if and only if you have the key to that vertex. It is guaranteed that $k_i$ forms a permutation. As long as you enter a vertex, you obtain the key inside that vertex. Once obtained, a key is never consumed. Now you have obtained the key to vertex $i$ and are at vertex $i$. For each $i$, you need to find: 1. How many vertices you can reach. 2. How many vertices you can reach and then return to the starting vertex $i$. **Please note: all given edges are directed edges!**

**This problem has multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains two integers $n, m$, representing the number of vertices and edges in the graph. The second line contains $n$ integers $k_1, k_2, \ldots, k_n$, meaning that vertex $i$ contains the key to vertex $k_i$. It is guaranteed that $k_i$ forms a permutation. The next $m$ lines each contain two integers $x, y$, indicating a directed edge from $x$ to $y$ in the graph. It is guaranteed that there are no multiple edges or self-loops.

For each test case, output $n$ lines. Each line contains two integers. On the $i$-th line, the integers represent the number of vertices reachable when starting from vertex $i$, and the number of vertices that are reachable and can return to the starting point.

**[Sample Explanation]** The following is the explanation for the first test case (the content in parentheses in the figure is the key number on the vertex).  1. The set of vertices that $1$ can reach is $\{1,2,3,4\}$, and the set of vertices that $1$ can reach and return to $1$ is $\{1,2,3,4\}$. 2. The set of vertices that $2$ can reach is $\{2,3\}$, and the set of vertices that $2$ can reach and return to $2$ is $\{2\}$. 3. The set of vertices that $3$ can reach is $\{3\}$, and the set of vertices that $3$ can reach and return to $3$ is $\{3\}$. 4. The set of vertices that $4$ can reach is $\{4\}$, and the set of vertices that $4$ can reach and return to $4$ is $\{4\}$. This is a valid traversal process: start from $1$, the initial key is $2$, reach vertex $2$ and obtain key $3$, reach vertex $3$ and obtain key $4$, return to vertex $1$, reach vertex $4$ and obtain key $1$, reach vertex $3$, and return to vertex $1$. **[Constraints]** For $100\%$ of the data, $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$. It is guaranteed that the graph contains no multiple edges or self-loops. **This problem uses bundled testdata and enables subtask dependencies!** |Subtask|Constraint on $n$|Constraint on $m$|Score|Dependency| |-|-|-|-|-| |1|$n\le 6$|$m\le 12$|$20$|\ | |2|$\sum n^3\le {10}^7$|$\sum m^3\le 2\times {10}^7$|$25$|\ | |3|$\sum n^2\le {10}^8$|$\sum m^2\le {10}^8$|$25$|Subtasks 1 and 2| |4|||$30$|Subtasks 1, 2, and 3| Translated by ChatGPT 5