W wolnym czasie Farmer John stworzył serwis udostępniania filmów MooTube. Jego krowy mogą nagrywać, udostępniać i odkrywać wiele zabawnych filmów. Opublikowały już $N$ filmów ($1 \leq N \leq 5000$), ponumerowanych $1 \ldots N$. FJ nie wie jednak, jak pomóc im znaleźć nowe filmy, które mogą im się spodobać.

FJ chce stworzyć listę „polecanych filmów” dla każdego filmu MooTube, aby polecać krowom filmy najbardziej związane z tymi, które już oglądają.

FJ wprowadza miarę „powiązania”, która, zgodnie z nazwą, określa, jak bardzo dwa filmy są ze sobą powiązane. Wybiera $N-1$ par i ręcznie oblicza ich powiązanie. Następnie przedstawia filmy jako sieć: każdy film jest wierzchołkiem, a $N-1$ rozpatrzonych par jest połączonych. Wybrał te $N-1$ par tak, aby między dowolnymi dwoma filmami istniała dokładnie jedna ścieżka połączeń. Powiązanie dowolnej pary definiuje jako najmniejsze powiązanie połączenia na tej ścieżce.

Farmer John chce wybrać $K$, aby przy każdym filmie MooTube polecano wszystkie pozostałe filmy o powiązaniu z nim co najmniej $K$. Obawia się jednak, że zbyt wiele rekomendacji odciągnie krowy od produkcji mleka! Dlatego chce starannie dobrać $K$. Pomóż odpowiedzieć na pytania o rekomendacje dla określonych wartości $K$.

Wejście

Pierwszy wiersz zawiera $N$ i $Q$ ($1 \leq Q \leq 5000$).

Następne $N-1$ wierszy opisuje pary ręcznie porównane przez FJ. Każdy zawiera trzy liczby całkowite $p_i$, $q_i$ i $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$): filmy $p_i$ i $q_i$ są połączone z powiązaniem $r_i$.

Następne $Q$ wierszy opisuje $Q$ pytań Farmer John. Każdy zawiera dwie liczby całkowite $k_i$ i $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): pytanie $i$ pyta, ile filmów poleci się widzom filmu $v_i$ przy $K = k_i$.

Wyjście

Wypisz $Q$ wierszy. W wierszu $i$ wypisz odpowiedź na pytanie $i$ FJ.

Przykład

Wejście 1

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

Wyjście 1

3
0
2

Uwagi

Powiązanie filmów1 i2 wynosi3, filmów2 i3 wynosi2, a filmów2 i4 wynosi4. Stąd powiązanie1 i3 to $min(3, 2) = 2$, 1 i4 to $min(3, 4) = 3$, a3 i4 to $min(2, 4) = 2$.

Farmer John chce poznać liczbę rekomendacji z filmu2 przy $K=1$, z filmu1 przy $K=3$ i z filmu1 przy $K=4$. Przy $K=1$ dla filmu2 polecane są filmy1,3 i4. Przy $K=4$ dla filmu1 nie poleca się żadnego filmu. Przy $K=3$ dla filmu1 poleca się filmy2 i4.

Autor zadania: Jay Leeds