Your country can be represented by \(N\) cities connected using \(N - 1\) roads. There exists an edge between city \((i,\ i+1)\) for all \(i\) from 1 to \(n - 1\).

You have to set up a connection for water supply. You set this in one city and water gets transported from it to other cities using road transport. Certain cities are blocked which means that water cannot pass through this city. Determine the maximum number of cities to which water can be supplied.

Input format

• The first line contains an integer \(N\) denoting the number of cities.
• The next \(N - 1\) lines contain two space-separated integers \(u\ v\) denoting a road between city \(u\) and \(v\).
• The next line contains N space-separated integers where it is 1 if the \(i^{th}\) city is blocked else 0.

Output format
Print a single integer denoting the maximum cities to which water can be supplied.

Constraints
\(1 \le N \le 2\times 10^5\)