$1$부터 $N$까지 $N$개의 정점으로 이루어진 무방향 트리가 있다.

트리에는 특별한 정점이 있다. 트리에 간선을 추가해서 모든 특별한 정점을 한 번씩 방문하는 경로를 만들려고 한다. 이때 같은 정점을 두 번 방문해서는 안된다. 특별한 정점이 아닌 일반 정점은 경로상에 포함될 수 있지만, 모든 일반 정점을 방문할 필요는 없다.

모든 특별한 정점을 한 번씩 방문하는 경로를 만들기 위해 필요한 간선의 최소 개수를 구해보자.

Input

첫째 줄에 정점의 개수 $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$번 정점은 특별한 정점이다.

입력으로 주어지는 그래프는 트리이다.

Output

경로를 만들기 위해 추가해야 할 간선의 최소 개수를 출력한다.

Examples

Input 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

Output 1

4

Input 2

4
1 2
2 3
3 4
0 0 0 0

Output 2

0

Input 3

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

Output 3

1