영역 게임

앨리스와 밥은 정점이 $n$개인 트리에서 게임을 하기를 좋아한다. 정점에는 $1, 2, \dots, n$ 번호가 붙어 있다. 두 사람은 총 $q$번의 게임을 한다.

$i$번째 게임에서 앨리스는 정점 $a_i$에서, 밥은 $a_i$와 다른 정점 $b_i$에서 시작한다. 처음에는 정점 $a_i$가 앨리스의 색으로, 정점 $b_i$가 밥의 색으로 칠해져 있고 나머지 정점에는 색이 없다.

그 뒤 두 사람은 차례대로 총 $k_i$번 움직인다. 앨리스가 첫 번째로 움직이고, 밥이 두 번째로 움직이며, 이후 앨리스가 세 번째 움직임을 하는 식이다. 한 번의 움직임에서 플레이어는 인접한 정점으로 이동하고 그 정점을 칠한다. 정점은 다시 칠해질 수 있으며, 어느 순간이든 칠해진 정점의 색은 가장 최근에 그곳에 도착한 플레이어의 색이다.

최종적으로 앨리스 색 정점의 수를 $A$, 밥 색 정점의 수를 $B$라고 하자. 앨리스는 $A - B$를 최대화하려 하고, 밥은 이 값을 최소화하려 한다. 각 게임에서 두 사람이 최적으로 플레이할 때 $A - B$의 값을 구하라.

입력에는 0개 이상의 테스트 케이스가 들어 있으며, 입력은 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 두 정수 $n$과 $q$가 주어진다 ($2 \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$).

이어지는 $n-1$개의 줄에는 각각 간선으로 연결된 두 정점 $u_i$, $v_i$가 주어진다 ($1 \le u_i, v_i \le n$). 입력은 트리임이 보장된다.

마지막 $q$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $k_i$가 주어진다 ($1 \le a_i, b_i \le n$, $1 \le k_i \le 2n$, $a_i \ne b_i$).

모든 테스트 케이스의 $n$ 합과 $q$ 합은 각각 $2 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스에 대해 차이 값을 나타내는 정수 하나를 출력한다.