25310번 - 곰곰이의 아르바이트

문제

배달하는 곰곰이

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

곰곰이의 나라에는 특이하게도 배달 주문을 들어온 순서대로 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$개의 줄에 걸쳐, 각 배달 주문별로 만들어질 수 있는 순서쌍의 개수를 출력한다.

제한

힌트