나무 위의 입자

트리는 사이클이 없는 연결 그래프다. 위 그림은 트리 모양의 입자가속기와 그 위의 한 정점에 놓인 특별한 입자를 나타낸다. RB 입자라고 부르는 이 입자는 안정한 상태에서 빨간색이고, 불안정해지면 1초마다 색이 바뀐다. 빨간색이었다면 검은색이 되고, 검은색이었다면 빨간색이 된다.

택희는 이 입자로 간단한 실험을 한다. 먼저 가속기 안에서 시작 정점과 끝 정점을 정하고, 안정한 입자를 하나 꺼내 불안정하게 만든 뒤 시작 정점에 놓는다. 이 준비에는 시간이 걸리지 않는다. 그 직후 입자는 끝 정점을 향해 최단 경로로 이동하며, 간선 하나를 지나는 데 정확히 1초가 걸린다.

택희는 실험을 $M$번 했지만 결과를 정리하지 못했다. 각 실험에 대해 택희가 기억하는 것은 두 가지다. 입자가 정점 $U$와 $V$를 잇는 간선을 $U$에서 $V$ 방향으로 지난 적이 있다는 사실, 그리고 끝 정점에 도착했을 때의 입자 색이다.

실험 보고서를 복원하려면 실험마다 조건에 맞는 (시작 정점, 끝 정점) 쌍이 몇 개인지 세어야 한다. 택희를 도와 그 개수를 구하자.

첫 줄에 입자가속기의 정점 수 $N$ ($2 \le N \le 10^5$)과 실험 횟수 $M$ ($1 \le M \le 10^5$)이 주어진다.

이어지는 $N-1$개의 줄에 간선으로 이어진 두 정점 $U$ $V$가 주어진다. ($1 \le U, V \le N$, $U \ne V$)

이어지는 $M$개의 줄에 실험 하나에 대해 알고 있는 정보 $U$ $V$ $C$가 주어진다. ($1 \le U, V \le N$, $C$는 0 또는 1, $U \ne V$)

이는 그 실험에서 입자가 $U$와 $V$를 잇는 간선을 $U$에서 $V$ 방향으로 지난 적이 있고, 끝 정점에서의 색이 $C = 0$이면 빨간색, $C = 1$이면 검은색이었다는 뜻이다.

시작 정점에서 입자는 항상 빨간색이다. 모든 실험에서 주어지는 $U$와 $V$에 대해 트리에 $U$와 $V$를 잇는 간선이 반드시 존재한다.

입력으로 주어지는 입자가속기는 항상 올바른 트리다.

$M$개의 줄을 출력한다.

$i$번째 줄에는 $i$번째 실험에서 가능한 서로 다른 (시작 정점, 끝 정점) 쌍의 개수를 출력한다.

계산 과정에서 값이 32비트 부호 있는 정수 범위를 넘을 수 있다.