给定一个由 $1$ 到 $N$ 共 $N$ 个顶点组成的无向树。

树中存在一些特殊顶点。我们希望通过在树中添加边，构造一条经过所有特殊顶点恰好一次的路径。在此过程中，不能访问同一个顶点两次。路径中可以包含非特殊顶点（即普通顶点），但不需要访问所有的普通顶点。

请计算为了构造出经过所有特殊顶点恰好一次的路径，所需添加的最少边数。

输入格式

第一行给定顶点的个数 $N$。$(1 \leq N \leq 200\,000)$

从第二行开始的 $N-1$ 行，每行给定两个顶点编号 $u, v$，表示一条边。$(1 \leq u, v \leq N)$

第 $N+1$ 行给定 $N$ 个由空格分隔的整数。如果第 $i$ 个整数为 $0$，则第 $i$ 号顶点为普通顶点；如果为 $1$，则第 $i$ 号顶点为特殊顶点。

输入给定的图是一棵树。

输出格式

输出为了构造该路径所需添加的最少边数。

样例

样例输入 1

21
1 2
1 3
2 4
2 5
3 6
3 7
3 8
3 9
4 10
5 11
5 12
6 13
6 14
10 15
10 16
13 17
16 18
16 19
17 20
17 21
0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0

样例输出 1

4

样例输入 2

4
1 2
2 3
3 4
0 0 0 0

样例输出 2

0

样例输入 3

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

样例输出 3

1