A Particle on the Tree

A tree is a connected graph with no cycle. The picture above shows a tree shaped particle accelerator and one special particle placed on a vertex of it. This particle, called an RB particle, is red while it is stable. Once it becomes unstable its color changes every second: red turns black, and black turns red.

Taekhee runs a simple experiment with it. He first fixes a start vertex and an end vertex inside the accelerator, takes one stable particle, makes it unstable, and puts it on the start vertex. That preparation takes no time. Right after that the particle moves toward the end vertex along a shortest path, and crossing one edge takes exactly 1 second.

Taekhee ran $M$ experiments but forgot to write the results down. For each experiment he remembers two things: that the particle crossed the edge between vertices $U$ and $V$ in the direction from $U$ to $V$, and the color of the particle when it arrived at the end vertex.

Restoring the report means counting, for each experiment, how many (start vertex, end vertex) pairs agree with what he remembers. Compute that count for him.

The first line has the number of vertices of the accelerator $N$ ($2 \le N \le 10^5$) and the number of experiments $M$ ($1 \le M \le 10^5$).

Each of the next $N-1$ lines has two vertices $U$ $V$ joined by an edge. ($1 \le U, V \le N$, $U \ne V$)

Each of the next $M$ lines has the information known about one experiment as $U$ $V$ $C$. ($1 \le U, V \le N$, $C$ is 0 or 1, $U \ne V$)

This means that in that experiment the particle crossed the edge between $U$ and $V$ in the direction from $U$ to $V$, and the color at the end vertex was red when $C = 0$ and black when $C = 1$.

The particle is always red at the start vertex. For every $U$ and $V$ given in an experiment, the tree is guaranteed to contain the edge between $U$ and $V$.

The accelerator given in the input is always a valid tree.

Print $M$ lines.

On line $i$, print the number of distinct (start vertex, end vertex) pairs that were possible in experiment $i$.

The value can exceed the range of a 32 bit signed integer during the computation.