After rigging the squirrel nation's election and obtaining full control over the nation, Wesley has ordered the imprisonment of his enemy Besley.

In order to regain his authority and power, Besley needs to escape from prison. Little does Wesley know, Besley has an accomplice (you) that has access to the prison's surveillance system, who will help Besley safely escape the prison without running into any guards.

The prison has ~N~ rooms labelled from ~1~ to ~N~, with ~N-1~ two-way passageways connecting pairs of rooms, with the ~i^{th}~ passageway connecting room ~x_i~ and ~y_i~. It is possible to travel between any pair of rooms using a series of passageways, and it can be shown that the shortest path between any two rooms is unique. Security is very tight, with guards patrolling a series of rooms connected with corridors. Running into any guard will result in severe punishment, which is why planning the escape will be a necessity.

Besley will ask you ~Q~ questions in the form of two pairs of integers ~(a_i, b_i)~ and ~(c_i, d_i)~, which asks that whether or not, and the earliest time he will encounter a guard if he is travelling from room ~a_i~ to room ~b_i~ and the guard moves from room ~c_i~ to room ~d_i~. Both Besley and the guard use the shortest path between the two rooms, and will only meet if they are both in the same room at the same time and neither of them have reached their destination room yet. They both leave their initial room at ~\text{time} = 0~ and take ~1~ second to move to an adjacent room.

Time is running out for Besley, can you quickly answer all his questions?

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

~2 \le N \le 200\,000~
~1 \le Q \le 200\,000~
~1 \le x_i, y_i \le N~ for all ~1 \le i \le N-1~
~1 \le a_i, b_i, c_i, d_i \le N~ for all ~1 \le i \le Q~
~a_i \neq b_i~ for all ~1 \le i \le Q~
~c_i \neq d_i~ for all ~1 \le i \le Q~
Only input where it is possible to travel between any pair of rooms using a series of passageways is allowed.

Subtask 1 [4%]

~2 \le N \le 2\,000~
~1 \le Q \le 2\,000~

Subtask 2 [9%]

~x_i = i~ for all ~1 \le i \le N-1~
~y_i = i+1~ for all ~1 \le i \le N-1~

Subtask 3 [18%]

~a_i = 1~ for all ~1 \le i \le Q~
~b_i = N~ for all ~1 \le i \le Q~
~d_i = N~ for all ~1 \le i \le Q~

Subtask 4 [18%]

~a_i = 1~ for all ~1 \le i \le Q~
~b_i = N~ for all ~1 \le i \le Q~

Subtask 5 [16%]

~b_i = N~ for all ~1 \le i \le Q~
~d_i = N~ for all ~1 \le i \le Q~

Subtask 6 [35%]

No additional constraints.

Input Specification

The first line of input contains ~2~ integers, ~N~ and ~Q~, representing the number of rooms in the prison, and the number of questions that Besley asks.

The next ~N-1~ lines describe the passageways. Each line contains ~2~ integers, ~x_i~ and ~y_i~, indicating a two-way passageway between rooms ~x_i~ and ~y_i~. Only input where it is possible to travel between any pair of rooms using a series of passageways is allowed.

The next ~Q~ lines describe the questions that Besley asks. Each line contains ~4~ integers, ~a_i~, ~b_i~, ~c_i~, and ~d_i~, indicating that Besley is asking whether or not, and the earliest time he will encounter a guard if he is travelling from room ~a_i~ to room ~b_i~ and the guard moves from room ~c_i~ to room ~d_i~.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output ~Q~ lines. The ~i^{th}~ line should contain the answer to the ~i^{th}~ question. If Besley will encounter a guard if he is travelling from room ~a_i~ to room ~b_i~ and the guard moves from room ~c_i~ to room ~d_i~, output a single integer equal to the earliest time that he will encounter the guard. Otherwise, output -1.

Sample Input 1

5 4
5 3
5 1
5 2
5 4
2 4 3 1
2 5 4 1
3 1 4 5
1 5 2 5

Sample Output 1

1
-1
-1
-1

Sample Explanation 1

For the first question, Besley will encounter the guard at ~\text{time} = 1~ in room ~5~.
For the second, third, and fourth questions, Besley will not encounter the guard before at least one of them reaches their destination.

Sample Input 2

4 3
1 2
2 3
3 4
1 3 2 4
2 3 3 2
1 4 3 1

Sample Output 2

-1
-1
1

Sample Input 3

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

Sample Output 3

-1
2

Sample Input 4

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

Sample Output 4

0
2

Sample Input 5

5 2
5 1
1 4
2 3
2 1
2 5 4 5
4 5 3 5

Sample Output 5

1
-1