시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB34141339.394%

문제

배달하는 곰곰이

심부름을 잘하는 곰곰이는 최근 배달 아르바이트를 할 기회를 얻었다.

곰곰이의 나라에는 특이하게도 배달 주문을 들어온 순서대로 2개씩 묶어 처리해야 한다는 법이 있어서, 곰곰이도 한 번 출발하면 2개의 도시를 순서대로 들러야 한다. 배달 주문 하나는 따라서 도시 3개의 튜플 $(A, B, C)$로 표현이 가능하고, 이는 곰곰이가 음식점이 있는 $A$도시에서 출발하여 $B$도시까지 최단경로로 이동, 다시 $B$도시에서 $C$도시까지 최단경로로 이동한다는 것을 의미한다. 곰곰이의 나라는 트리 형태이고, 따라서 $N$개의 도시가 $N-1$개의 양방향 도로로 이어져 있으며 연결그래프를 이룬다.

치킨을 좋아하는 곰곰이는 이번에도 역시 기회가 될 때마다 닭 다리를 사려고 한다. 곰곰이는 이동하는 중간에 들르는 도시에서 닭 다리를 구매할 수 있으며, 각 도시에서는 최대 한 개의 닭 다리를 구매할 수 있다. 배달 주문을 완료하는 시점에는 닭 다리가 정확히 두 개 있어야 한다.

곰곰이는 배달 주문을 처리할 때마다, 노트에 자신이 닭 다리를 산 도시의 순서쌍을 적어둔다. 예를 들어 $3$번 도시에서 닭 다리를 산 뒤, $1$번 도시에서 닭 다리를 샀으면 $(3, 1)$로 표기한다.

각 주문별로 만들어질 수 있는 순서쌍의 개수를 구해보자.

입력

첫째 줄에 도시의 개수 $N$, 배달 주문의 개수 $Q\ (1 \leq N, Q \leq 100\,000)$가 공백을 사이에 두고 주어진다.

둘째 줄부터 $N-1$줄에 걸쳐 정수 $u$, $v$ 가 공백을 사이에 두고 주어진다. 이는 $u$ 도시와 $v$ 도시를 잇는 양방향 도로가 있음을 의미한다. $(1 \leq u, v \leq N)$

$N+1$째 줄부터 $Q$개의 줄에 걸쳐 배달 주문 $(A, B, C)$의 정수 $A, B, C$ $(1 \le A, B, C \le N)$ 가 공백을 사이에 두고 주어진다.

출력

$Q$개의 줄에 걸쳐, 각 배달 주문별로 만들어질 수 있는 순서쌍의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

11
0
3

예제 입력 2

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

예제 출력 2

11
6
1
18
7

출처