| Codeforces Round 429 (Div. 1) |
|---|
| Закончено |
Леха попал в дерево из n вершин с корнем в вершине под номером 1. На каждой вершине i написано целое число ai. Его не выпустят пока он не ответит на q запросов вида u v. Ответ на запрос это максимальное значение 
, среди всех вершин i на пути от u до v, включая u и v, где dist(i, v) — количество рёбер на пути от i до v. Так же гарантируется, что вершина u является предком вершины v. Лехины вкусы очень специфичны: Он считает, что вершина является предком самой себя.
Помогите Лехе выйти.
Выражение 
означает применение побитового исключающего ИЛИ к числам x и y.
Напомним, что вершина u является предком вершины v, если вершина u лежит на пути от корня до вершины v.
В первой строке содержится два целых числа n и q (1 ≤ n ≤ 5·104, 1 ≤ q ≤ 150 000) — количество вершин в дереве и количество запросов соответственно.
Следующая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ n) — числа на вершинах.
Каждая из следующих n - 1 строк содержит по два целых числа u и v (1 ≤ u, v ≤ n) — описание очередного ребра дерева.
Гарантируется, что данный граф является деревом.
Следующие q строк содержат по два целых числа u и v (1 ≤ u, v ≤ n) — описание очередного запроса. Гарантируется, что вершина u является предком вершины v.
Выведите q строк — ответы на запросы.
5 3
0 3 2 1 4
1 2
2 3
3 4
3 5
1 4
1 5
2 4
3
4
3
5 4
1 2 3 4 5
1 2
2 3
3 4
4 5
1 5
2 5
1 4
3 3
5
5
4
3
