Mojtaba has two trees, each of them has $n$ vertices. Arpa has $q$ queries, each in type $v, u, x, y$. Let $s$ be the set of vertices in the path from $v$ to $u$ in the first tree and $p$ be the set of vertices in the path from $x$ to $y$ in the second tree. Mojtaba has to calculate the size of $s \cap p$ for each query. Help him!

Input Format

The first line of input will contain two integers, $n, q$ ($1 \le n, q \le 3 \cdot 10^5$).

The next $n-1$ lines will contain edges of the first tree.

The next $n-1$ lines will contain edges of the second tree.

The next $q$ lines contain queries.

Output Format

For each query, let $s$ be the set of vertices in the path from $v$ to $u$ in the first tree and $p$ be the set of vertices in the path from $x$ to $y$ in the second tree, print the size of $s \cap p$ for each query.