问题背景

小杨有一棵包含n个节点的树，节点从1到n编号，并且每个节点是要么白色，要么黑色。

对于树上的一条简单路径（不经过重复节点的路径），小杨认为其美丽的当且仅当路径上相邻的节点的颜色均不相同。

例如如下情况：其中节点1和节点4是黑色，其他节点是白色，路径2-1-3-4是美丽路径，而路径2-1-3-5不是美丽路径（相邻节点3和5颜色相同）。

问题描述

小杨想知道整棵树中的最长美丽路径长度是多少。

格式

输入

第一行包含一个正整数n，代表节点数量。

第二行包含n个整数c1, c2, …, cn，代表每个节点的颜色。如果ci=0，代表节点i为白色。如果ci=1，代表节点i为黑色。

之后n-1行，每行包含两个正整数ui, vi，代表存在一条连接节点ui和vi的边。

输出

输出一个整数，代表最长美丽路径的长度。

样例

输入数据 1

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

输出数据 1

4

输入数据 2

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

输出数据 2

1

提示

对于全部数据，保证： 1 ≤ n ≤ 10^5，0 ≤ ci ≤ 1，且保证给出的数据构成一棵树。