405342: GYM101908 L Subway Lines

The subway system of a major city is formed by a set of stations and tunnels that connect some pairs of stations. The system was designed so that there is exactly one sequence of tunnels linking any pair of stations. The stations for which there is only one tunnel passing through are called terminals. There are several train lines that make round trips between pairs of terminal stations, passing only through the stations in the unique path between them. People are complaining about the current lines. Therefore, the mayor ordered that the lines are redefined from scratch. As the system has many stations, we need to help the engineers, who are trying to decide which pair of terminals will define a line.

The figure illustrates a system where terminal stations are shown as filled circles and the non-terminals are shown as empty circles. On the leftmost picture, if the pair $$$(A, B)$$$ define a line and the pair $$$(C, D)$$$ defines another, they won't have any common station. But, on the rightmost picture, we can see that if the pairs $$$(E, F)$$$ and $$$(G, H)$$$ are chosen, those two lines will have two stations in common.

Given the description of the system and a sequence of $$$Q$$$ queries consisting of two pairs of terminals, your program should compute, for each query, how many stations the two lines defined by those pairs have in common.

The first line of the input contains two integers $$$N$$$ ($$$5 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 20000$$$), representing respectively the number of stations and the number of queries. The stations are numbered from 1 to $$$N$$$. Each of the following $$$N−1$$$ lines contains two distinct integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$), indicating that there is a tunnel between stations $$$U$$$ and $$$V$$$. Each of the following $$$Q$$$ lines contains four distinct integers $$$A, B, C, D$$$ ($$$1 \leq A, B, C, D \leq N$$$), representing a query: the two train lines are defined by pairs $$$(A, B)$$$ and $$$(C, D)$$$.

For each query, your program must print a line containing an integer representing how many stations the two train lines defined by the query would have in common.

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

1

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

0
4
0
3