지하철 노선

대도시의 지하철 시스템은 여러 역과, 일부 역 쌍을 잇는 터널로 이루어져 있다. 시스템은 어떤 두 역을 잇는 터널의 경로가 정확히 하나가 되도록 설계되었다. 터널이 하나만 연결된 역을 종점이라 한다. 두 종점 사이를 왕복하는 여러 열차 노선이 있으며, 두 종점 사이의 유일한 경로를 따라 운행한다. 시민들이 현재 노선에 불만을 제기하자 시장은 노선을 전면 개편하라고 명령했다. 역이 매우 많기 때문에, 어떤 종점 쌍이 노선을 정의할지 결정하려는 엔지니어들을 도와야 한다.

그림은 종점을 채워진 원으로, 종점이 아닌 역을 빈 원으로 나타낸 시스템을 보여 준다. 왼쪽을 보면 (A,B) 쌍이 한 노선을, (C,D) 쌍이 다른 노선을 정의하면 두 노선은 공통 역을 갖지 않는다. 그러나 오른쪽에서는 (E,F) 쌍과 (G,H) 쌍이 두 노선을 정의하면 두 역을 공통으로 갖는다.

터널 시스템의 설명과 두 종점 쌍으로 이루어진 Q개의 질의가 주어질 때, 각 질의마다 두 쌍이 정의하는 노선이 공통으로 갖는 역이 몇 개인지 계산하는 프로그램을 작성하라.

첫째 줄에는 두 정수 N (5 ≤ N ≤ 105)과 Q (1 ≤ Q ≤ 20000)가 주어지며, 각각 역의 수와 질의의 수를 나타낸다. 역은 1부터 N까지 번호가 매겨진다. 다음 N −1개 줄에는 서로 다른 두 정수 U와 V (1 ≤ U, V ≤ N)가 주어지며, 역 U와 V 사이에 터널이 있음을 나타낸다. 다음 Q개 줄에는 서로 다른 네 정수 A, B, C, D (1 ≤ A, B, C, D ≤ N)가 주어지며, 하나의 질의를 나타낸다. 두 열차 노선은 쌍 (A, B)와 (C, D)로 정의된다.

각 질의마다, 그 질의가 정의하는 두 열차 노선이 공통으로 갖는 역의 수를 나타내는 정수 하나를 한 줄에 출력한다.