Maximum Lucky XOR on a Tree Path

A country A has \(n\) cities, connected by \(n-1\) roads in such a way that there is a unique path between any two cities (i.e. the cities form a tree). Each city has a lucky number represented by a monument at its center. Travel-planners plan to fly into city \(x\) and then travel along the unique path from city \(x\) to city \(y\), before flying out from city \(y\). As they pass through each city on the path, they have the option to take a photo with the city's lucky number. They believe that the lucky numbers combine using the bitwise \(\operatorname{xor}\) operation. In other words, if a traveler takes photos in some of the cities and the corresponding lucky numbers are \(a_1, a_2, \dots, a_k\), then the final lucky value is \(a_1 \operatorname{xor} a_2 \operatorname{xor} \cdots \operatorname{xor} a_k\).

Since the travelers can choose to take a photo or not at each city they visit, they would like to know the maximum lucky value they can achieve along the journey from \(x\) to \(y\). For example, if the lucky numbers along the path are 5, 7, and 11, then by choosing the photos from cities with lucky numbers 5 and 11, the final lucky value is \(5 \operatorname{xor} 11 = 14\), which is maximum for this set.

Your task is to compute the maximum lucky value that can be obtained from the lucky numbers along the unique path between two given cities \(x\) and \(y\) in the tree.

inputFormat

The input is given as follows:

 n
 x y
 a1 a2 ... an
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)

Where:

• \(n\) is the number of cities.
• \(x\) and \(y\) are the starting and ending cities of the traveler's journey.
• \(a_i\) is the lucky number of the \(i\)-th city.
• Each of the next \(n-1\) lines contains two integers \(u_i\) and \(v_i\) indicating a bidirectional road between cities \(u_i\) and \(v_i\).

outputFormat

Output a single integer, which is the maximum lucky value (i.e. the maximum possible XOR sum) that can be obtained by choosing a subset of lucky numbers on the unique path from \(x\) to \(y\).

sample

3
1 3
1 2 3
1 2
2 3

3