MuTub (Gümüş)

Giriş

Birinci sətirdə iki tam ədəd $n$ və $q (1 \leq n, q \leq 5000)$ q~(1 \le n, q \le 5000) — uyğun olaraq video çarxlarının sayı və sorğuların sayı verilir.

Növbəti $n - 1$ n − 1 sətirdə fermer Conun əl ilə qiymətləndirdiyi video cütləri arasındakı relevantlıq təsvir olunur. Hər sətirdə üç tam ədəd $p_{i}, q_{i}$ p_i, q_i və $r_{i} (1 \leq p_{i}, q_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ r_i~(1 \le p_i, q_i \le n, 1 \le r_i \le 10^9) verilir ki, bu da $p_{i}$ p_i və $q_{i}$ q_i nömrəli video çarxlarının relevantlığı $r_{i}$ r_i olan kənarla birləşdiyini bildirir.

Sonra isə fermer Conun hər sorğusunu təsvir edən $q$ sətir verilir. $i$ -ci sətirdə iki tam ədəd $k_{i}$ k_i və $v_{i} (1 \leq k_{i} \leq 1 0^{9}, 1 \leq v_{i} \leq n)$ v_i~(1 \le k_i \le 10^9, 1 \le v_i \le n) verilir — bu, $i$ -ci sorğuda FC-nin, tövsiyələrin minimal icazə verilən relevantlığı $k = k_{i}$ k = k_i olduqda, $v_{i}$ v_i nömrəli video üçün neçə videonun tövsiyə olunacağı ilə maraqlandığını bildirir.

Çıxış

$q$ sətir çap edin. $i$ -ci sətirdə FC-nin $i$ -ci sualına cavabı çap edin.

Nümunələr

Fermer Con videolar arasında aşağıdakı əlaqələri qurmuşdur:

$1$ və $2$ nömrəli videoların relevantlığı $3$ -dür,
$2$ və $3$ nömrəli videoların relevantlığı — $2$ ,
$2$ və $4$ nömrəli videoların relevantlığı — $4$ .

Bu məlumatlar əsasında digər video cütləri arasındakı relevantlığı hesablamaq olar:

$1$ və $3$ nömrəli videolar: relevantlıq = $min (3, 2) = 2$ min(3, 2) = 2,
$1$ və $4$ nömrəli videolar: relevantlıq = $min (3, 4) = 3$ min(3, 4) = 3,
$3$ və $4$ nömrəli videolar: relevantlıq = $min (2, 4) = 2$ min(2, 4) = 2.

İndi isə aşağıdakı sorğularda hansı videoların tövsiyə olunacağına baxaq:

$k = 1$ k = 1 olduqda $2$ nömrəli videodan $1, 3$ və $4$ nömrəli videolar tövsiyə olunacaq.
$k = 3$ k = 3 olduqda $1$ nömrəli videodan $2$ və $4$ nömrəli videolar tövsiyə olunacaq.
$k = 4$ k = 4 olduqda $1$ nömrəli videodan heç bir video tövsiyə olunmayacaq.

Nümunə 1

Loading