Background

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.

Problem Description

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!

Input Format

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.

Output Format

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.

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

Hint

[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!

Translated by ChatGPT 5