No tempo livre, Farmer John criou um serviço de partilha de vídeos chamado MooTube. As suas vacas podem gravar, partilhar e descobrir muitos vídeos divertidos. Já publicaram $N$ vídeos ($1 \leq N \leq 5000$), numerados $1 \ldots N$. Porém, FJ não sabe como ajudá-las a encontrar novos vídeos de que gostem.

FJ quer criar uma lista de «vídeos sugeridos» para cada vídeo MooTube, recomendando os vídeos mais relevantes para os que as vacas já veem.

FJ define uma medida de «relevância» que indica, como o nome sugere, quanto dois vídeos se relacionam. Escolhe $N-1$ pares e calcula manualmente a relevância de cada par. Depois representa os vídeos como uma rede: cada vídeo é um nó e os $N-1$ pares estudados estão ligados. Escolheu esses $N-1$ pares de forma que existe exatamente um caminho de ligações entre quaisquer dois vídeos. Define a relevância de qualquer par como a menor relevância de uma ligação nesse caminho.

Farmer John quer escolher $K$ para que, junto de qualquer vídeo MooTube, sejam sugeridos todos os outros vídeos cuja relevância para ele seja pelo menos $K$. Contudo, receia que demasiadas sugestões distraiam as vacas da produção de leite! Por isso, pretende escolher cuidadosamente $K$. Ajude-o a responder a perguntas sobre sugestões para determinados valores de $K$.

Entrada

A primeira linha contém $N$ e $Q$ ($1 \leq Q \leq 5000$).

As $N-1$ linhas seguintes descrevem os pares comparados manualmente. Cada uma contém três inteiros $p_i$, $q_i$ e $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$), indicando que os vídeos $p_i$ e $q_i$ estão ligados com relevância $r_i$.

As $Q$ linhas seguintes descrevem as $Q$ perguntas de Farmer John. Cada uma contém dois inteiros $k_i$ e $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): a pergunta $i$ pede quantos vídeos serão sugeridos aos espectadores do vídeo $v_i$ se $K = k_i$.

Saída

Imprima $Q$ linhas. Na linha $i$, imprima a resposta à pergunta $i$ de FJ.

Exemplos

Entrada 1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

Saída 1

3
0
2

Nota

A relevância dos vídeos1 e2 é3, dos vídeos2 e3 é2 e dos vídeos2 e4 é4. Assim, a dos vídeos1 e3 é $min(3, 2) = 2$, a dos vídeos1 e4 é $min(3, 4) = 3$ e a dos vídeos3 e4 é $min(2, 4) = 2$.

Farmer John quer saber quantos vídeos serão sugeridos a partir do vídeo2 se $K=1$, do vídeo1 se $K=3$ e do vídeo1 se $K=4$. Com $K=1$, os vídeos1,3 e4 são sugeridos no vídeo2. Com $K=4$, nenhum vídeo é sugerido no vídeo1. Com $K=3$, os vídeos2 e4 são sugeridos no vídeo1.

Autor do problema: Jay Leeds