Nicole is planning her routine for the rhythmic gymnastics.

Currently, her ability can be described as a collection of poses, and two-way transitions between these poses. She has simplified her skillset so that using the transitions, there is only a single path between any pair of poses. In other words, she can choose any start and end pose, and there is a unique combination of transitions that take her from the starting pose to the ending pose.

Nicole is considering adding a new transition to her skillset, which would now allow her some options when getting from pose A to pose B. It would be interesting to know just how many pairs of poses require less transitions to get between them, if this new transition was added.

Input

Input will begin with two integers ~n~ (~2 \leq n \leq 3\times 10^5~) and ~q~ (~1 \leq q \leq 5000~) - the number of poses in Nicole's skillset, and the number of queries.

~n-1~ lines will follow, containing 2 distinct integers each, corresponding with the transitions between poses.

~q~ lines will follow, containing 2 distinct integers each, representing a prospective transition. You can be guaranteed this transition is not present in the original skillset.

You can be guaranteed that ~n \times q \leq 3\times 10^6~ for all test cases.

Output

Output ~q~ lines containing a single integer per each query - the number of distinct pairs of poses that would require less transitions to get between the two poses, if the prospective transition was included in Nicole's skillset.

A pair of poses is distinct if at least one pose is present in one but not the other - so ~(a, b)~ is not distinct from ~(b, a)~.

Example 1

Input

7 3
4 1
2 3
3 4
5 7
3 5
4 6
1 7
1 6
4 5

Output

4
1
6