높은 나무에서 내려오지 못하는 Praveen

Praveen은 높은 나무에 올라갔는데 지금 내려올 수 없다. Arjun이 사다리를 가져올 때까지 기다리면서, 그는 트리의 $N$개 정점에 $1$부터 $N$까지 번호를 붙이고 각 정점에 값 $S[i]$를 하나씩 연결하며 시간을 보내기로 했다. 이를 위해 다음 절차를 수행한다.

val = 1
Let T be our tree.
while T is not empty:
  Identify the branching nodes of tree T. A node of tree T is said to be a branching node if its degree > 2.
  Choose all the nodes of T which have a path to any leaf node not passing through any of the branching nodes.
  Remove all of these chosen nodes from the tree T.
    Set S value of all these removed nodes to be val.
  Increase val by 1, i.e. val += 1

분기 정점을 찾는 첫 단계는 while 루프가 실행될 때마다 다시 수행된다.

Praveen은 실제로 트리에서 정점을 제거할 수 없다. 머릿속의 슈퍼컴퓨터에서 절차를 시뮬레이션할 뿐이다.

Arjun이 사다리를 들고 돌아온 뒤, Praveen은 트리에 관한 $Q$개의 질의를 던진다. 각 질의는 두 정점 $u$, $v$를 담고 있다. 트리에서 $u$에서 $v$로 가는 경로를 $u, u_1, u_2, \ldots, u_r, v$라고 하자. 배열 $S[u], S[u_1], \ldots, S[u_r], S[v]$를 보자. 각 질의마다 Arjun은 이 배열의 역전쌍 개수를 구해야 한다. 두 인덱스 $i$, $j$가 $i > j$이고 $S[i] < S[j]$이면 역전쌍을 이룬다.

Praveen은 Arjun이 모든 질의에 답할 때까지 내려오지 않겠다고 버틴다. Arjun은 머릿속에 슈퍼컴퓨터가 없고 노트북도 집에 두고 왔다. 그러니 질의에 답해서 Praveen을 내려보내 주자.

입력의 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 문제에서 정의한 $N$과 $Q$가 공백으로 구분되어 주어진다. 다음 $N - 1$개 줄에는 정점 $u$와 $v$ 사이에 간선이 있음을 뜻하는 두 정수 $u$, $v$가 주어진다. 다음 $Q$개 줄에는 질의의 두 정점 $u$, $v$가 주어진다.

각 테스트 케이스마다 $Q$개의 질의에 대한 답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 10^5$
• $1 \le N, Q \le 10^5$
• $1 \le u, v \le N$
• 모든 테스트 케이스의 $N$ 합과 $Q$ 합은 각각 $10^5$을 넘지 않는다.