题目背景

溯洄从之，道阻且长。溯游从之，宛在水中央。——《诗经·秦风·蒹葭》

题目描述

给定一张 $n$ 个点，$m$ 条边的有向图，点从 $1\sim n$ 编号。图中每个点 $i$ 有点权 $p_i$。注意可能有重边自环。

如果点 $u$ 出发存在路径到达点 $v$，则你可以将 $u,v$ 的点权交换。

对于每个点 $i$，输出使 $i$ 点权最大化的最少交换次数。请注意，每个回答是独立的，即都应该从初始给定的图开始交换。

输入格式

请注意，此题需要较快的输入输出方式，并且在实现过程中，请注意常数对程序效率的影响。

第一行输入整数 $n,m$ 表示有向图的点数和边数。

第二行输入 $n$ 个整数 $p_1\sim p_n$。

接下来 $m$ 行，每行两个整数 $u,v$ 表示一条点 $u$ 指向点 $v$ 的有向边。

输出格式

输出一行，依次表示使 $1,2,\dots,n$ 号点点权最大化的最少交换次数。

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

0 0 1 0 1 0

提示

样例 #1 解释

可以证明，$6$ 个点的点权的最大可能值分别为 $1,1,5,5,5,4$。

使 $1$ 号点点权最大化的方案：不交换。

使 $2$ 号点点权最大化的方案：不交换。

使 $3$ 号点点权最大化的方案：交换 $3$ 号和 $4$ 号点的点权。

使 $4$ 号点点权最大化的方案：不交换。

使 $5$ 号点点权最大化的方案：交换 $4$ 号和 $5$ 号点的点权。

使 $6$ 号点点权最大化的方案：不交换。

数据范围

对于所有数据，保证 $1\le n,m\le 5\times10^5,1\le p_i\le10^9,1\le u,v\le n$。注意可能有重边自环。

• Subtask 1（5pts）：$n,m\le3$。
• Subtask 2（25pts）：$n,m\le10^3$。
• Subtask 3（8pts）：图为一条链。即对于所有 $i=1,2,\dots,n-1$，$i$ 与 $i+1$ 之间有且仅有一条有向边，但方向不确定。
• Subtask 4（12pts）：图为一棵树。即 $m=n-1$，且图将有向边改成无向边后连通。
• Subtask 5（20pts）：$n,m\le5\times10^4$，且图随机生成。随机生成方式见下。
• Subtask 6（10pts）：$n,m\le10^5$。
• Subtask 7（20pts）：$n,m\le5\times10^5$。

Subtask 5 的随机生成方式：

• 先确定 $n,m$ 和序列 $p$（不一定随机）。
• 然后对于 $m$ 条边，每条边的 $u,v$ 都在 $1\sim n$ 的整数中均匀随机取。

请注意，此题需要较快的输入输出方式，并且在实现过程中，请注意常数对程序效率的影响。