Primary Factor

"Which is the highest mountain in the world? The highest point on the summit of Mount Everest. OK, but which is the second highest mountain in the world? The second highest point on the summit of Mount Everest, of course."

With that logic, the list of the world's highest mountains becomes very silly. But there is a solution: introduce the concept of a primary factor. The primary factor of a mountain is the smallest height difference you must descend from the mountain to reach a strictly higher mountain. It works as a kind of measure of how independent a mountain is, and if you remove every point with a primary factor less than 200 m, you get rid of all the silly little mountains that really sit on higher mountains. This problem is about finding all primary factors in a graph.

We have a graph with $n$ nodes and $m$ edges, where each node $i$ has a non-negative integer $h(i)$, the height of the node. The primary factor $P(i)$ of a node is the smallest height you must descend from the node to reach a node of strictly greater height. Here is a slightly more mathematical definition: let $G(i)$ be the set of all paths from node $i$ to some other node $j$ such that $h(j) > h(i)$. The primary factor of $i$ is defined as

$P(i) = \min_{\gamma \in G(i)} \left\{ h(i) - \min_{k\in \gamma}(h(k)) \right\}$

If $G(i) = \emptyset$, that is, if it is impossible to reach a node of greater height at all, we say that the primary factor is $h(i)$.

Given a graph, find the primary factors of all nodes.

One line with two integers, $n$ and $m$. One line with $n$ integers $0 \leq h(i) \leq 10^9$, the heights of the nodes. $m$ lines with two integers, $a$ and $b$ ($1 \leq a,b \leq n$), meaning that an edge goes between nodes $a$ and $b$.

One line with $n$ integers, the primary factors of the nodes.

• $n \le 100\,000$
• $m \le 400\,000$