МуТуб (Gümüş)

"'markdown Boş vaxtlarında fermer Con yeni bir video paylaşma xidməti yaratdı və ona MooTube adını verdi. MooTube-da fermer Conun inəkləri çoxlu əyləncəli videoları qeyd edə, paylaşa və kəşf edə bilərlər. Onun inəkləri artıq $n$ videonu ardıcıl nömrələrlə $\mathrm{1...}n$ yerləşdiriblər. Lakin Con inəklərinə xoşlarına gələ biləcək yeni videolar tapmaqda necə kömək edəcəyini tam başa düşmür.

Con, MooTube-da hər bir video üçün "tövsiyə olunan videolar" siyahısı yaratmaq istəyir. Beləliklə, inəklərə artıq izlədikləri videolara ən uyğun olan videolar tövsiyə olunacaq.

Con, iki videonun bir-birinə nə qədər uyğun olduğunu müəyyən edən "əlaqəlilik" metrikasını inkişaf etdirir. O, $n-1$ video cütünü seçir və onların cüt-cüt uyğunluğunu əl ilə hesablayır. Sonra Con videolarını bir şəbəkə kimi vizuallaşdırır, burada hər bir video bir düyündür və əl ilə nəzərdən keçirdiyi $n-1$ video cütü ilə bağlıdır. Rahatlıq üçün Con öz $n-1$ cütlərini elə seçib ki, hər hansı bir video digər videodan birləşmələr yolu ilə yalnız bir şəkildə əldə edilə bilsin. Con qərara alır ki, hər hansı bir video cütü üçün əlaqəlilik, bu yoldakı hər hansı bir birləşmənin minimal əlaqəliliyi kimi müəyyən edilməlidir.

Fermer Con, MooTube-da hər hansı bir verilmiş videoya yaxın olan və bu videoya ən az $k$ əlaqəliliyi olan bütün digər videoların təklif olunması üçün $k$ dəyərini seçmək istəyir. Lakin Con narahatdır ki, inəklərinə çoxlu video təklif olunacaq, bu da onların süd istehsalından yayındıra bilər! Buna görə də, uyğun $k$ dəyərini diqqətlə təyin etmək istəyir. Fermer Con, müəyyən $k$ dəyərləri üçün təklif olunan videolar haqqında bir sıra suallara cavab vermək üçün sizin köməyinizə ehtiyac duyur.

Giriş verilənləri

Birinci sətir $n(1\le n\le 5000)$ və $q(1\le q\le 5000)$ ədədlərini ehtiva edir. Növbəti $n-1$ sətir Conun əl ilə müqayisə etdiyi video cütlərini təsvir edir. Hər bir sətir üç tam ədəd $p_i,q_i$ və $r_i(1\le p_i,q_i\le n,1\le r_i\le 10^9)$ ehtiva edir ki, bu da $p_i$ və $q_i$ videolarının $r_i$ əlaqəliliyi ilə bağlı olduğunu göstərir.

Növbəti $q$ sətir fermer Conun $q$ sorğusunu təsvir edir. Hər bir sətir iki tam ədəd $k_i$ və $v_i(1\le k_i\le 10^9,1\le v_i\le n)$ ehtiva edir — bu o deməkdir ki, $i$-ci sorğuda Con $k=k_i$ olduqda $v_i$ videosuna neçə video təklif olunacağını soruşur.

Çıxış verilənləri

$q$ sətir çıxarın. $i$-ci sətirdə Conun $i$-ci sualına cavabı çıxarın.

Nümunələr

Fermer Con aşkar edir ki, birinci və ikinci videoların əlaqəliliyi $3$, ikinci və üçüncü videoların əlaqəliliyi $2$, ikinci və dördüncü videoların əlaqəliliyi $4$-dür. Buna görə də, birinci və üçüncü videoların əlaqəliliyi $min(3,2)=2$, birinci və dördüncü videoların əlaqəliliyi $min(3,4)=3$, üçüncü və dördüncü videoların əlaqəliliyi $min(2,4)=2$-dir.

Fermer Con, $k=1$ olduqda ikinci videodan neçə video təklif olunacağını, $k=3$ olduqda birinci videodan neçə video təklif olunacağını və $k=4$ olduqda birinci videodan neçə video təklif olunacağını bilmək istəyir. Görürük ki, $k=1$ olduqda ikinci videoda $1,3$ və $4$ videoları təklif olunacaq. $k=4$ olduqda birinci videodan heç bir video təklif olunmayacaq. Lakin $k=3$ olduqda birinci videodan $2$ və $4$ videoları təklif olunacaq. "'