题目描述

给定一棵有 $n$ 个顶点的无向树。每个顶点 $v$ 上记录了一个非负整数 $a_v$，满足 $0 \le a_v < 2^k$。

如果一个顶点集合中所有顶点的 $a$ 值按位或等于 $2^k-1$，则称这个集合是好的。

一个集合的代价定义为集合中任意两点距离的最大值，其中树上两点距离为它们之间唯一简单路径上的边数。

你需要求出一个好集合的最小代价，或判断不存在好集合。

输入格式

第一行包含两个整数 $n,k$（$2 \le n \le 100000$，$1 \le k \le 20$），表示树的顶点数和参数 $k$。

第二行包含 $n$ 个整数 $a_i$（$0 \le a_i < 2^k$），表示每个顶点的值。

接下来 $n-1$ 行描述树边。第 $i$ 行包含两个整数 $v_i,u_i$（$1 \le v_i,u_i \le n$），表示第 $i$ 条边连接的两个顶点。

输出格式

如果不存在好集合，输出 -1。否则输出一个整数，表示好集合的最小代价。

样例

样例输入 1

5 3
1 2 6 0 4
1 2
2 3
1 4
3 5

样例输出 1

2

样例输入 2

3 3
0 1 2
1 2
2 3

样例输出 2

-1

样例解释

第一个样例中，可以选择顶点集合 $\{1,2,3\}$。

第二个样例中，能够得到的最大按位或值为 $3$，无法达到 $2^3-1=7$。

计分方式

测试数据包含九个测试组。只有当某组所有测试点以及该组要求的若干前置组均通过时，才能获得该组分数。注意，某些测试组不要求通过样例测试。离线测试表示该组测试结果会在比赛结束后才可见。