МуТуб (Qızıl)
Fermer Con boş vaxtlarında yeni bir video paylaşma platforması yaratdı və ona MooTube adını verdi. MooTube-da Conun inəkləri bir çox maraqlı videolar çəkib paylaşa və yeni videolar kəşf edə bilərlər. Onun inəkləri artıq n ardıcıl nömrələnmiş video yerləşdiriblər, 1-dən n-ə qədər. Lakin Con, inəklərinə maraqlı videolar tapmaqda necə kömək edəcəyini tam başa düşmür.
Con, MooTube-da hər video üçün "tövsiyə olunan videolar" siyahısı yaratmaq istəyir. Beləliklə, inəklərə izlədikləri videolara ən uyğun olan videolar tövsiyə ediləcək.
Con, iki videonun bir-birinə nə qədər uyğun olduğunu müəyyən edən bir "əlaqəlilik" metrikası hazırlayır. O, n - 1 video cütlüyü seçir və onların uyğunluğunu əl ilə hesablayır. Sonra Con, videoları bir şəbəkə kimi təsvir edir, burada hər video bir düyündür və o, əl ilə nəzərdən keçirdiyi n - 1 video cütlüyü ilə bağlıdır. Rahatlıq üçün Con öz n - 1 cütlüyünü elə seçib ki, hər hansı bir video digər videodan yalnız bir yol ilə əldə edilə bilsin. Con qərara alır ki, hər hansı bir video cütlüyünün əlaqəliliyi bu yoldakı hər hansı bir əlaqənin minimal əlaqəliliyi kimi müəyyən edilməlidir.
Fermer Con, MooTube-da verilmiş hər hansı bir video ilə yanaşı, bu videoya ən az k əlaqəliliyi olan bütün digər videoların təklif edilməsi üçün k dəyərini seçmək istəyir. Lakin Con narahatdır ki, inəklərinə çoxlu video təklif edilə bilər, bu da onları süd istehsalından yayındıra bilər! Buna görə də o, uyğun k dəyərini diqqətlə təyin etmək istəyir. Fermer Conun müəyyən k dəyərləri üçün təklif olunan videolar haqqında bir sıra suallara cavab verməyinizə ehtiyacı var.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 100000) və q (1 ≤ q ≤ 100000) ədədlərini ehtiva edir. Növbəti n − 1 sətir Conun əl ilə müqayisə etdiyi video cütlüyünü təsvir edir. Hər sətir üç tam ədəd p[i], q[i] və r[i] (1 ≤ p[i], q[i] ≤ n, 1 ≤ r[i] ≤ 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 sətir iki tam ədəd k[i] və v[i] (1 ≤ k[i] ≤ 10^9, 1 ≤ v[i] ≤ n) ehtiva edir - bu, i-ci sorğuda Conun k = k[i] olduqda v[i] videosundan neçə video təklif ediləcəyini soruşduğunu bildirir.
Çıxış Məlumatları
q sətir çıxarın. i-ci sorğuya cavab olaraq i-ci sətirdə cavabı çıxarın.
Nümunə
Fermer Con birinci və ikinci videoların 3 əlaqəliliyi, ikinci və üçüncü videoların 2 əlaqəliliyi, ikinci və dördüncü videoların isə 4 əlaqəliliyi olduğunu aşkar edir. Buna əsasən, 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 isə min(2, 4) = 2 olur.
Fermer Con ikinci videodan k = 1, birinci videodan k = 3 və birinci videodan k = 4 olduqda neçə video təklif ediləcəyini bilmək istəyir. Görürük ki, k = 1 olduqda, 1, 3 və 4 videoları ikinci videodan təklif ediləcək. k = 4 olduqda, birinci videodan heç bir video təklif edilməyəcək. Lakin k = 3 olduqda, birinci videodan 2 və 4 videoları təklif ediləcək.