Первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 100\,000$, $1 \le m \le 100\,000$)~--- количество людей, включая Сашу, и количество дружеских связей между людьми.

Вторая строка содержит $n - 1$ целых чисел $a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)~--- моменты времени, когда каждый из людей начинает писать своим друзьям.

Третья строка содержит $n - 1$ целых чисел $t_2, \dots, t_n$ ($1 \le t_i \le 10^9$)~--- периоды, с которыми каждый человек пишет своим друзьям.

В каждой из следующих $m$ строк содержится два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$)~--- номера дружащих людей.

Гарантируется, что пары дружащих людей не повторяются, то есть $(u_i, v_i) \ne (u_j, v_j)$ и $(u_i, v_i) \ne (v_j, u_j)$, если $i \ne j$.

Гарантируется, что в результате процесса, описанного в условии, с каждым человеком в конце концов проведут воспитательную беседу.