题目描述

在一个含有 $n$ 个点 $n$ 条边的无重边无自环的连通无向图中，有一个扫地机器人在执行清扫作业。其中结点 $i$ 的标记 $t_i \in \{0,1\}$：如果为 $1$，则说明该结点需要进行清扫，扫地机器人在到达这个结点时会顺便进行清扫工作。机器人想知道，如果选定任意结点出发，每条边只能经过一次的话，最多能清扫多少个待清扫结点？

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数 $t_1, t_2, \cdots, t_n$，相邻整数之间使用一个空格分隔。

接下来 $n$ 行，每行包含两个正整数 $u_i, v_i$，用一个空格分隔，表示结点 $u_i$ 和结点 $v_i$ 之间有一条边。

输出格式

输出一行包含一个整数表示答案。

9
1 0 1 0 0 1 1 0 1
2 8
2 9
2 5
1 5
1 3
1 4
4 5
4 6
6 7

4

提示

样例说明

其中一种可行路线：$3 \rightarrow 1 \rightarrow 4 \rightarrow 6 \rightarrow 7$，清扫结点 $3, 1, 6, 7$（共 $4$ 个）。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 5000$；
• 对于所有评测用例，$1 \leq n \leq 500000$，$t_i \in \{0,1\}$，$1 \leq u_i, v_i \leq n$。