题目描述

给定一棵包含 $2n$ 个结点的树，结点由 $1 \sim 2n$ 编号。结点 $i$ 带有颜色 $c_i\in\{0,1,2\}$。

树上的每条边带权值，初始时边权均为 $0$。

首先，对于所有满足 $c_i=0$ 的结点 $i$，你需要将其颜色改为 $1$ 或 $2$。

然后，你需要找出恰好 $n$ 组结点的匹配。设第 $i$ 组匹配为 $(x_i,y_i)$。需要满足：

• $x_1,x_2,\cdots,x_n,y_1,y_2,\cdots,y_n$ 为 $1 \sim 2n$ 的排列。
• 对于所有 $1 \le i \le n$，有 $c_{x_i}=1,c_{y_i}=2$。

然后对于所有 $1 \le i \le n$，进行以下操作：

• 将树上从结点 $x$ 至结点 $y$ 路径上所有边的权值加 $1$。

最后，你需要找出一个整数 $m$，使得不存在任何一条边的权值 $> m$。

请求出 $m$ 的最小值。

输入格式

第一行一个整数 $n$。

第二行 $2n$ 个整数 $c_1,c_2,\cdots,c_{2n}$。

接下来 $2n-1$ 行，每行两个整数 $u,v$ 表示一条树边。

输出格式

仅一行，表示 $m$ 可能的最小值。

样例

2
1 0 0 2
1 2
2 3
3 4

1

说明/提示

对于 $100\%$ 的数据：

• $1 \le n \le 2 \times 10^5$；
• $c_i \in \{0,1,2\}$；
• $\sum_{i=1}^{2n} [c_i=1] \le n$；
• $\sum_{i=1}^{2n} [c_i=2] \le n$。

本题开启捆绑测试。

• Subtask #1（$5 \ \text{pts}$）：$n \le 7$，不存在 $a_i=0$。
• Subtask #2（$20 \ \text{pts}$）：不存在 $a_i=0$。
• Subtask #3（$10 \ \text{pts}$）：$a_i=0$ 的结点 $i$ 的个数不超过 $9$ 个，$n \le 10^4$。
• Subtask #4（$5 \ \text{pts}$）：结点 $1$ 的度数为 $2n-1$。
• Subtask #5（$25 \ \text{pts}$）：$n \le 800$。
• Subtask #6（$10 \ \text{pts}$）：每个结点的度数均 $\le 2$。
• Subtask #7（$25 \ \text{pts}$）：无特殊限制。