Description

Given a directed graph with $n$ vertices and $m$ edges, numbered from $1$ to $n$, with no guarantee of no duplicate edges or self-loops. Each vertex $i$ has a weight $p_i$.

If there exists a path from vertex $u$ to vertex $v$, you can swap the weights of $u$ and $v$.

For each vertex $i$, output the minimum number of swaps needed to maximize the weight of vertex $i$. Note that each answer is independent, meaning the swaps should be considered starting from the initial graph each time.

Input Format

Note that this problem requires efficient input and output methods, and during implementation, attention should be paid to the impact of constants on program efficiency.

The first line contains two integers $n,m$ representing the number of vertices and edges in the directed graph.

The second line contains $n$ integers $p_1,p_2,\dots,p_n$.

The next $m$ lines each contain two integers $u,v$ representing a directed edge from vertex $u$ to vertex $v$.

Output Format

Output a line containing the minimum number of swaps needed to maximize the weight of each vertex $1,2,\dots,n$ in sequence.

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

0 0 1 0 1 0

Hint

Sample #1 Explanation

It can be proven that the maximum possible weights for the $6$ vertices are $1,1,5,5,5,4$, respectively.

• To maximize the weight of vertex $1$: No swaps needed.
• To maximize the weight of vertex $2$: No swaps needed.
• To maximize the weight of vertex $3$: Swap the weights of vertices $3$ and $4$.
• To maximize the weight of vertex $4$: No swaps needed.
• To maximize the weight of vertex $5$: Swap the weights of vertices $4$ and $5$.
• To maximize the weight of vertex $6$: No swaps needed.

Data Range

For all data, it is guaranteed that $1\le n,m\le 5\times10^5,1\le p_i\le10^9,1\le u,v\le n$. No guarantee of no duplicate edges or self-loops.

Note that this problem requires bundled testing.

• Subtask 1 (5pts): $n,m\le3$.
• Subtask 2 (25pts): $n,m\le10^3$.
• Subtask 3 (8pts): The graph is a chain. That is, for all $i=1,2,\dots,n-1$, there is exactly one directed edge between $i$ and $i+1$, but the direction is uncertain.
• Subtask 4 (12pts): The graph is a tree. That is, $m=n-1$, and After converting the graph into an undirected graph, it becomes connected.
• Subtask 5 (20pts): $n,m\le5\times10^4$, and the graph is randomly generated. The random generation method is described below.
• Subtask 6 (10pts): $n,m\le10^5$.
• Subtask 7 (20pts): $n,m\le5\times10^5$.

Random generation method for Subtask 5:

• First, determine $n,m$ and the sequence $p$ (not necessarily random).
• Then, for each of the $m$ edges, select $u,v$ uniformly at random from the integers $1$ to $n$.

Note that this problem requires efficient input and output methods, and during implementation, attention should be paid to the impact of constants on program efficiency.