30749번 - Дома в Берляндии 다국어

문제

Как известно, в столице Берляндии есть $n$ перекрёстков. На некоторых их этих перекрёстков находятся жилые дома. Пусть $a_i$ --- это количество человек в семье, проживающей в доме, который находится на перекрёстке $i$ для всех 1ドル \leq i \leq n$. Если $a_i$ равно нулю, будем считать, что на этом $i$-м перекрёстке нет жилого дома.

Некоторые перекрёстки соединены дорогами. Всего в Берляндии $m$ дорог. По каждой дороге можно ходить в любом направлении. Каждая дорога соединяет два различных перекрёстка. Любые два перекрёстка соединены не более чем одной дорогой. От любого перекрёстка можно добраться по дорогам города до любого другого перекрёстка. Назовём расстоянием между перекрёстками $i$ и $j$ минимальное количество дорог, по которым нужно пройти, чтобы добраться от перекрёстка $i$ до перекрёстка $j$.

Когда одна семья ходит в гости к другой семье, каждый человек находит себе ровно одного собеседника из другой семьи, и они вдвоем разговаривают между собой. Двум семьям общаться скучно, если какой-то человек останется без собеседника.

По какой-то непонятной причине правительство Берляндии попросило вас найти два ближайших жилых дома $v$ и $u,ドル таких что если семья из дома $v$ придёт в гости к семье из дома $u,ドル то им будет скучно общаться, то есть $a_v > 0,ドル $a_u > 0,ドル $a_v \ne a_u$ и расстояние от $v$ до $u$ минимально. Гарантируется, что существуют два жилых дома с различным количеством жильцов.

입력

В первой строке входных данных заданы числа $n$ и $m$ (2ドル \leq n \leq 1,000円,000,円 1 \leq m \leq 1,000円,000円$) --- количество перекрёстков в столице Берляндии и количество двунаправленных дорог соответственно.

Во второй строке входных данных заданы $n$ чисел (0ドル \leq a_i \leq 10^9$), где $a_i$ равно 0ドル,ドル если на $i$-м перекрёстке нет жилого дома, или $a_i$ равно количеству человек в семье, проживающей в доме, который находится на $i$-м перекрёстке.

В следующих $m$ строках заданы дороги. В $i$-й из этих строк заданы два числа $v_i$ и $u_i$ (1ドル \leq v_i, u_i \leq n, v_i \ne u_i$) --- номера перекрёстков, соединённых соответствующей дорогой.

출력

В единственной строке выведите одно целое число --- минимальное расстояние между двумя жилыми домами с различным количеством жильцов.

제한

노트

В первом примере населены только два дома --- у перекрёстков 1ドル$ и 3ドル$ и количество жильцов в них разное. Расстояние между домами равно 2ドル,ドル кратчайший путь использует дороги 1ドル$ и 2ドル$.