햇빛

Noah는 1부터 $n$까지 번호가 붙은 정점 $n$개로 이루어진 루트가 없는 트리를 가지고 있습니다. 매일 아침 Noah는 햇빛의 영향을 받을 두 정점 $u$와 $v$를 고릅니다. 영향은 간선을 따라 퍼지지만, $w$개보다 많은 간선을 지나면 사라집니다.

각 날마다 햇빛의 영향을 받는 정점의 개수를 구하세요. 입력은 암호화되어 있으므로, 풀이는 온라인으로 동작해야 합니다.

첫 줄에 테스트 케이스의 개수 $T$가 주어집니다.

각 테스트 케이스의 첫 줄에는 $n$과 $m$이 주어집니다. 이어지는 $n-1$개의 줄에는 정점 $u$와 $v$를 잇는 간선이 하나씩 주어집니다.

$lastans$는 전날의 답입니다. 각 테스트 케이스가 시작될 때 $lastans$는 0입니다. 이어지는 $m$개의 줄에는 $u'$, $v'$, $w'$가 주어지며, 실제 값은 다음과 같습니다.

$u = ((u' + lastans) \bmod n) + 1,\quad v = ((v' + lastans) \bmod n) + 1,\quad w = (w' + lastans) \bmod n$

제약 조건: $1 \le T \le 100$, $1 \le n, m \le 10^5$, $1 \le u, v, u', v' \le n$, $0 \le w' < n$.

$n, m \le 10^3$을 만족하지 않는 테스트 케이스는 10개 이하이며, 입력 파일은 32 MiB를 넘지 않습니다.

각 날의 답을 한 줄에 하나씩 출력하세요.

출력 파일은 7 MiB를 넘지 않습니다.

복호화된 값은 다음과 같습니다. 1일차: $u = 1$, $v = 2$, $w = 0$. 2일차: $u = 1$, $v = 2$, $w = 1$. 3일차: $u = 1$, $v = 2$, $w = 2$. 4일차: $u = 1$, $v = 2$, $w = 3$. 5일차: $u = 1$, $v = 2$, $w = 4$.