항공사

항공사는 서로 다른 공항 $n$개를 잇는 정기 항공편을 운항한다. 각 항공편은 두 공항을 직접 연결하며(다른 공항에 들르지 않는다), 양방향으로 이동할 수 있다. 임의의 출발 공항 $s$와 도착 공항 $t$에 대해, 어떤 공항도 두 번 방문하지 않고 둘을 잇는 항공편 경로가 정확히 하나 존재하도록 배치되어 있다. 이 경로를 이루는 항공편의 수를 $s$와 $t$ 사이의 거리라고 한다.

항공사가 공항 $x$와 $y$ 사이에 항공편을 하나 추가하면, 일부 $(s, t)$ 쌍에서 더 짧은 경로가 생길 수 있다. 영향을 받는 쌍이 많을수록 새 노선의 가치가 높다. 항공사는 이 기준으로 추가 후보 $(x, y)$ 여러 개를 평가해 달라고 요청했다.

첫 줄에 정수 $n$과 $q$가 주어진다. 다음 $n-1$개 줄에는 정수 $u_i$, $v_i$가 주어지며, 공항 $u_i$와 $v_i$를 잇는 직항 항공편이 기존에 있다는 뜻이다. 마지막 $q$개 줄에는 정수 $x_i$, $y_i$가 주어진다. $i$번째 시나리오에서는 기존 $n-1$개 항공편에 $x_i$와 $y_i$를 잇는 직항 항공편이 추가된다.

$q$개 줄을 출력한다. $i$번째 줄에는 $1 \le s < t \le n$을 만족하는 쌍 $(s, t)$ 중, 기존 $n-1$개 항공편에 $x_i$와 $y_i$를 잇는 직항 항공편을 추가했을 때 $s$와 $t$ 사이의 거리가 줄어드는 쌍의 개수를 출력한다.

• $2 \le n \le 10^6$
• $1 \le q \le 10^5$
• $1 \le u_i \le n$; $1 \le v_i \le n$; $u_i \ne v_i$
• $1 \le x_i \le n$; $1 \le y_i \le n$; $x_i \ne y_i$
• $\sum_{i=1}^{q} d_i \le 10^7$. 여기서 $d_i$는 기존 항공망에서 $x_i$와 $y_i$ 사이의 거리이다.