P13823 「Diligent-OI R2 C」Where's She I Need

> Upstream I go, the way is long. Downstream I go, she's there among. ——_The Book of Songs: Qin Feng: Reeds_

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.**

**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 a line containing the minimum number of swaps needed to maximize the weight of each vertex $1,2,\dots,n$ in sequence.

#### 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.**