Reachability in a Directed Graph with Key Unlocking

You are given a directed graph with n vertices and m edges. In addition, each vertex i contains a key for another vertex k_i. The array k is a permutation of {1, 2, ..., n}.

You can enter vertex v only if you currently possess the key for vertex v. Once you enter a vertex, you immediately obtain the key that is stored in that vertex. Keys, once obtained, are never consumed.

You start the process at vertex i with the key for vertex i. Moreover, because you are already at vertex i, you also pick up the key contained in vertex i (i.e. k_i). Using the keys you have, you may travel along the directed edges of the graph as long as you are allowed to enter the destination vertex (i.e. you already have its key). Note that the unlocking condition applies at every step.

Your task is: for each starting vertex i (1 ≤ i ≤ n), compute two values:

1. The total number of vertices that can be reached (visited) using the above process.
2. The number of vertices among these reached vertices from which there is a valid path back to the starting vertex i if we only allow moves between vertices that were reached. (In other words, if you restrict the graph to the set of reached vertices, count the number of vertices that can return to i via one or more directed moves.)

Important: All edges are directed.

inputFormat

The first line contains two integers n and m — the number of vertices and the number of edges.

The second line contains n integers k_1, k_2, ..., k_n, which form a permutation of {1, 2, ..., n}.

Then follow m lines, each containing two integers u and v indicating there is a directed edge from vertex u to vertex v.

outputFormat

Output n lines. The i-th line should contain two integers separated by a space: the number of reachable vertices from vertex i according to the process, and the number of vertices (among those reached) from which you can return to vertex i using only the reached vertices.

sample

3 3
2 3 1
1 2
2 3
3 1

3 3
3 3
3 3