题目内容

小塔的朋友送了他一棵节点数为 $n$ 的糖果树($1$号点为根节点)，树上的每个糖果都有一个颜色。

小塔吃糖果有一个习惯，他每次都会吃掉一整个子树的糖果，他喜欢与众不同，所以每次吃之前他都会把出现次数最多的颜色的糖果扔掉(可能有多个出现次数最多的颜色，此时要全部扔掉)，他可以选择任意一棵子树吃掉，但他只能吃一次，因此他想知道他一次能吃到的所有糖果的颜色的异或和最大是多少(如果吃到了多个颜色相同的糖果，也需要做多次异或)，你能帮帮他吗?

输入描述

第一行一个整数$n(1 ≤ n ≤ 1000)$。表示树的节点数量。

第二行$n$个整数$a_i(1 ≤a_i ≤ n)$，表示节点$i$的颜色。

接下来$n-1$行，每行两个整数$u,v$表示节点$u$和节点$v$之间有一条边。

输出描述

输出仅有一行，一个整数表示他一次能吃到的糖果的颜色的异或和最大值。

样例1

输入

4
1 2 3 4
1 2
2 3
2 4

输出

0

说明

四个节点颜色各不相同。吃掉任意子树都会在吃之前把所有糖果扔掉，因此结果为$0$。

样例2

输入

4
1 1 2 2
1 2
2 3
2 4

输出

1

说明

吃掉以节点$3$或节点$4$为根的子树都只有一个节点，结果都为$0$，以$1$为根节点时颜色为$1$和颜色为$2$的节点数量都为$2$，因此结果也为$0$。

吃掉以$2$为根的子树时节点$3$和节点$4$颜色都为$2$被删除，结果为节点$2$的颜色$1$。