Problem Statement

You are given a tree $T$ with $N$ vertices numbered $1$ through $N$, and an $N \times N$ matrix $A = (A_{i,j})$. The $i$-th edge of $T$ connects vertices $U_i$ and $V_i$. Each entry of $A$ is $0$ or $1$.

Define the score of an integer sequence $x=(x_1,x_2,\dots,x_N)$ as follows:

• For a vertex pair $(i,j)(1 \le i,j \le N)$, let the simple path in $T$ from $i$ to $j$ be $v_1=i,v_2,\dots,v_n=j$ (this path is unique since $T$ is a tree). The pair $(i,j)$ is called a palindromic pair if $x_{v_k} = x_{v_{n+1-k}}$ for every $k(1 \le k \le n)$.
• If there exists a pair $(i,j)$ such that $A_{i,j} = 1$ and $(i,j)$ is not a palindromic pair, then the score of $x$ is $10^{100}$.
• Otherwise, the score of $x$ is the number of pairs $(i,j)$ such that $1 \le i,j \le N$ and $(i,j)$ is a palindromic pair.

Find the minimum score over all integer sequences $x$.

Constraints

• $1 \le N \le 3000$
• $1 \le U_i,V_i \le N$
• $T$ is a tree.
• $A_{i,j} \in \lbrace 0,1 \rbrace$
• $A_{i,i} = 1$
• $A_{i,j} = A_{j,i}$

Input

The input is given from Standard Input in the following format:

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Output the minimum score over all integer sequences $x$.