Statement is not available in English language
F. 특별한 정점
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

Input

첫째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 200 000)

둘째 줄부터 N - 1개의 줄에 걸쳐 간선이 연결하는 두 정점의 번호 u,v가 주어진다. (1 ≤ u, v ≤ N)

N + 1번째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. i번째 정수가 0이면 i번 정점은 일반 정점이며, 1이면 i번 정점은 특별한 정점이다.

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

Output

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

Examples
Input
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
4
Input
4
1 2
2 3
3 4
0 0 0 0
Output
0
Input
6
1 2
1 3
2 4
3 5
6 3
1 1 0 1 1 1
Output
1