In seiner Freizeit hat Farmer John einen Videodienst namens MooTube erstellt. Seine Kühe können dort viele lustige Videos aufnehmen, teilen und entdecken. Sie haben bereits $N$ Videos ($1 \leq N \leq 5000$), nummeriert mit $1 \ldots N$, veröffentlicht. FJ weiß jedoch nicht, wie er ihnen neue Videos finden helfen kann, die ihnen gefallen könnten.

FJ möchte für jedes MooTube-Video eine Liste „empfohlener Videos“ erstellen, um den Kühen die zu bereits angesehenen Videos relevantesten Videos zu empfehlen.

FJ entwickelt ein Maß für „Relevanz“, das angibt, wie stark zwei Videos zusammenhängen. Er wählt $N-1$ Paare und berechnet deren Relevanz von Hand. Dann stellt er die Videos als Netzwerk dar: Jedes Video ist ein Knoten, die $N-1$ betrachteten Paare sind verbunden. Diese $N-1$ Paare sind so gewählt, dass es zwischen zwei beliebigen Videos genau einen Weg von Verbindungen gibt. Die Relevanz eines beliebigen Paares definiert er als die kleinste Relevanz einer Verbindung auf diesem Weg.

Farmer John möchte $K$ so wählen, dass neben jedem MooTube-Video alle anderen Videos mit Relevanz mindestens $K$ zu diesem Video empfohlen werden. Zu viele Empfehlungen könnten die Kühe jedoch von der Milchproduktion ablenken! Deshalb will er $K$ sorgfältig passend wählen. Hilf ihm, Fragen zu Empfehlungen für bestimmte Werte von $K$ zu beantworten.

Eingabe

Die erste Zeile enthält $N$ und $Q$ ($1 \leq Q \leq 5000$).

Die nächsten $N-1$ Zeilen beschreiben die von Hand verglichenen Paare. Jede enthält drei ganze Zahlen $p_i$, $q_i$ und $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$): Videos $p_i$ und $q_i$ sind mit Relevanz $r_i$ verbunden.

Die nächsten $Q$ Zeilen beschreiben Farmer Johns $Q$ Fragen. Jede enthält zwei ganze Zahlen $k_i$ und $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): Frage $i$ fragt, wie viele Videos Zuschauern von Video $v_i$ bei $K = k_i$ empfohlen werden.

Ausgabe

Gib $Q$ Zeilen aus. In Zeile $i$ steht die Antwort auf FJs Frage $i$.

Beispiele

Eingabe 1

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

Ausgabe 1

3
0
2

Hinweis

Die Relevanz der Videos1 und2 ist3, der Videos2 und3 ist2 und der Videos2 und4 ist4. Daher ist die Relevanz von1 und3 gleich $min(3, 2) = 2$, von1 und4 gleich $min(3, 4) = 3$ und von3 und4 gleich $min(2, 4) = 2$.

Farmer John möchte wissen, wie viele Videos von Video2 bei $K=1$, von Video1 bei $K=3$ und von Video1 bei $K=4$ empfohlen werden. Bei $K=1$ werden für Video2 die Videos1,3 und4 empfohlen. Bei $K=4$ wird für Video1 keines empfohlen. Bei $K=3$ werden für Video1 die Videos2 und4 empfohlen.

Aufgabenautor: Jay Leeds