Pendant son temps libre, Farmer John a créé un service de partage de vidéos nommé MooTube. Ses vaches peuvent y enregistrer, partager et découvrir beaucoup de vidéos amusantes. Elles ont déjà publié $N$ vidéos ($1 \leq N \leq 5000$), numérotées $1 \ldots N$. Cependant, FJ ne sait pas comment les aider à trouver de nouvelles vidéos qui pourraient leur plaire.

FJ veut créer une liste de « vidéos suggérées » pour chaque vidéo MooTube, afin de recommander les vidéos les plus pertinentes par rapport à celles déjà regardées.

FJ définit une mesure de « pertinence » qui indique, comme son nom l'annonce, le degré de rapport entre deux vidéos. Il choisit $N-1$ paires et calcule manuellement leur pertinence. Il représente ensuite les vidéos par un réseau : chaque vidéo est un sommet et les $N-1$ paires étudiées sont reliées. Ces $N-1$ paires sont choisies de sorte qu'il existe exactement un chemin entre toute paire de vidéos. La pertinence de deux vidéos est le minimum des pertinences des liaisons de ce chemin.

Farmer John veut choisir $K$ pour suggérer, à côté de chaque vidéo MooTube, toutes les autres vidéos dont la pertinence par rapport à elle est au moins $K$. Mais trop de suggestions risquent de distraire les vaches de la production de lait ! Il veut donc choisir soigneusement $K$. Aidez-le à répondre à des questions sur les suggestions pour certaines valeurs de $K$.

Entrée

La première ligne contient $N$ et $Q$ ($1 \leq Q \leq 5000$).

Les $N-1$ lignes suivantes décrivent les paires comparées manuellement. Chaque ligne contient trois entiers $p_i$, $q_i$ et $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$), indiquant que les vidéos $p_i$ et $q_i$ sont reliées avec une pertinence $r_i$.

Les $Q$ lignes suivantes décrivent les $Q$ questions de Farmer John. Chaque ligne contient deux entiers $k_i$ et $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$) : la question $i$ demande combien de vidéos seront suggérées aux spectateurs de la vidéo $v_i$ lorsque $K = k_i$.

Sortie

Affichez $Q$ lignes. À la ligne $i$, affichez la réponse à la question $i$ de FJ.

Exemples

Entrée 1

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

Sortie 1

3
0
2

Remarque

La pertinence entre les vidéos1 et2 vaut3, entre2 et3 vaut2 et entre2 et4 vaut4. Ainsi, celle entre1 et3 vaut $min(3, 2) = 2$, entre1 et4 vaut $min(3, 4) = 3$ et entre3 et4 vaut $min(2, 4) = 2$.

Farmer John veut connaître le nombre de suggestions depuis la vidéo2 si $K=1$, depuis la vidéo1 si $K=3$ et depuis la vidéo1 si $K=4$. Si $K=1$, les vidéos1,3 et4 sont suggérées pour la vidéo2. Si $K=4$, aucune vidéo n'est suggérée pour la vidéo1. Si $K=3$, les vidéos2 et4 sont suggérées pour la vidéo1.

Auteur du problème : Jay Leeds