Cities

In a far away kingdom, there are $N$ cities numbered between $0$ and $N - 1$. The cities are connected by $N - 1$ two-way roads. Each road has the same length, and connects exactly two cities, such that there is a unique path between any pair of cities.

For any two cities $A$ and $B$, denote by $L(A, B)$ the number of roads of this unique path between cities $A$ and $B$. Given an integer $K$, for how many pairs of cities $A, B$ is $L(A, B) = K$?

The sample judge reads input in the following format:

• line $1$: N K
• line $2$: F[0] F[1] .. F[N - 2]
• line $3$: T[0] T[1] .. T[N - 2]

The sample judge will write a single line with the return value of paths(N, K, F, T).

• $1 \le K \le N \le 100\\,000$