Houses in Berland

The capital of Berland has $n$ crossroads. Some of them have residential houses. Let $a_i$ be the number of people in the family living in the house at crossroad $i$, for all $1 \le i \le n$. If $a_i$ is 0, crossroad $i$ has no house.

Some crossroads are connected by roads. Berland has $m$ roads. Each road can be traveled in either direction. Each road connects two different crossroads, and any two crossroads are connected by at most one road. You can reach any crossroad from any other crossroad by roads. The distance between crossroads $i$ and $j$ is the minimum number of roads on a path from $i$ to $j$.

When one family visits another, each person pairs up with exactly one person from the other family, and the two talk together. Two families find the visit boring if some person is left without a partner.

For reasons unknown, the government of Berland asks you to find two residential houses $v$ and $u$ such that if the family in house $v$ visits the family in house $u$, the visit is boring. That means $a_v > 0$, $a_u > 0$, $a_v \ne a_u$, and the distance from $v$ to $u$ is minimal. It is guaranteed that two residential houses with different numbers of residents exist.

The first line contains $n$ and $m$ ($2 \le n \le 1000000$, $1 \le m \le 1000000$), the number of crossroads and the number of two-way roads.

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$).

Each of the next $m$ lines contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$, $v_i \ne u_i$), the crossroads connected by the $i$-th road.

Print one integer: the minimum distance between two residential houses with different numbers of residents.

In the first example, only crossroads 1 and 3 have houses, and their residents differ. The distance between them is 2, and the shortest path uses roads 1 and 2.