Bobo 有一棵包含 $n$ 个顶点的树 $T$，顶点编号为 $1, 2, \dots, n$。每个顶点上都有一个盒子。Bobo 想要利用一个机器人将顶点 $i$ 上的盒子移动到顶点 $p_i$。

机器人最初位于顶点 $1$。在单位时间内，它可以沿边移动到相邻顶点，且最多可以携带当前顶点上的一个盒子。最后，机器人必须回到顶点 $1$。

求完成任务所需的最短时间。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_1, p_2, \dots, p_n \le n, p_i \neq p_j$)。 接下来的 $(n - 1)$ 行中，第 $i$ 行包含两个整数 $a_i, b_i$，表示顶点 $a_i$ 和 $b_i$ 之间有一条边。

输出格式

输出一个整数，表示最短时间。

样例

样例输入 1

3
1 3 2
1 2
2 3

样例输出 1

4

样例输入 2

4
2 1 4 3
1 3
3 2
3 4

样例输出 2

6