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.