该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

You are given a tree with $n$ vertices. Each edge is directed, and its direction represents the line of sight. We say that a vertex $u$ can see a vertex $v$ if and only if there is a directed path $u\to\ldots\to v$. Note that the direction of an edge only affects visibility, not movement. In other words, if there is a directed edge $u\to v$, you are allowed to move both from $u$ to $v$ and from $v$ to $u$.

You have missions on $q$ days. The mission on day $i$ is denoted by $c_i\to d_i$, meaning that you must move from $c_i$ to $d_i$. If you reach $d_i$ at time $t$, your mission is considered successful at time $t+1$ and at all subsequent times.

However, a hunter searches for you every day. On day $i$, the hunter follows the simple path from $a_i$ to $b_i$. After reaching $b_i$, the hunter remains there until the end of the day.

Each day starts at time $0$, when you and the hunter set out simultaneously from $c_i$ and $a_i$, respectively. Traversing an edge takes $1$ unit of time for both of you. At each time step, you may either move along one edge or remain at your current vertex. The hunter always moves along the specified route unless he has already reached his destination $b_i$, in which case he remains there. If the hunter can see you at any time, you are discovered and the mission fails.

For each day's mission, find the earliest time at which it can be completed. If it is impossible to complete the mission, output -1.

Format

Input

The first line contains two positive integers $n,q\,(1\le n\le 10^5, 1\le q\le 100)$, denoting the number of vertices and the number of days, respectively.

Each of the next $n-1$ lines contains two positive integers $u,v$, denoting a directed edge $u\to v$.

Each of the next $q$ lines contains four integers $a,b,c,d$, describing the mission for one day as specified above.

Output

Output $q$ lines. The $i$-th line should contain the earliest time at which the mission on day $i$ can be completed. If the mission cannot be completed, output -1.

Samples

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

2
3
-1

12 1
2 1
1 3
1 4
5 3
6 5
2 7
8 6
6 9
10 5
11 9
12 11
12 7 8 4

10