Kazak Vus və bayram

Potokolyandiya krallığının sakinləri dəqiqliyi ilə tanınırlar. Bayramların mükəmməl keçməsi üçün, onların cədvəli yüz il əvvəldən hazırlanıb. Kazak Vus dostu Kazak Vuhu krallığın bir şəhərinə dəvət etməyə və mümkün qədər çox bayramda iştirak etməyə qərar verib.

Krallıqda $n$ şəhər var və bunlar $n-1$ ikitərəfli yolla birləşdirilib. Bu yollar elə qurulub ki, hər hansı bir şəhərdən digərinə, bəlkə də başqa şəhərləri ziyarət edərək, çatmaq mümkündür. $i$-ci yoldan keçmək üçün $l_i$ gün tələb olunur.

Potokolyandiyada hər bir bayram, keçiriləcəyi şəhərin nömrəsi $c_i$ və bayramın keçiriləcəyi günün nömrəsi $d_i$ ilə müəyyən edilir. Kazak Vuh bayram etmək üçün çox vaxt sərf etmir. Əgər o, $i$-ci gün bayram edirsə, həmin gün yola çıxıb, növbəti gün başqa bir şəhərə gedə bilər (əgər $l_i=1$ olan bir yol varsa) və orada bayram edə bilər (əgər belə bir bayram varsa).

Kazak Vusun dostu elə xoşbəxt insandır ki, onun krallığa gəliş günü təqvimdə $0$ nömrəsi ilə qeyd olunur və əvvəlcə krallığın istənilən şəhərinə gələ bilər. Kazak Vus dostunun maksimum neçə bayramda iştirak edə biləcəyini öyrənmək istəyir. Ona kömək edin!

Giriş formatı

Birinci sətir krallığın şəhərlərinin sayını göstərən bir tam ədəd $n$ ($1\le n\le 2\cdot 10^5$) ehtiva edir.

Növbəti $n-1$ sətirin hər biri üç tam ədəd $a_i$, $b_i$ və $l_i$ ($1\le a_i,b_i\le n$, $1\le l_i\le 10^9$) ehtiva edir - yolun birləşdirdiyi şəhərlərin nömrələri və onu keçmək üçün lazım olan günlərin sayı. Qrafın əlaqəli olduğu təmin edilir.

Növbəti sətir krallıqda bayramların sayını göstərən bir tam ədəd $m$ ($1\le m\le 2\cdot 10^5$) ehtiva edir.

Növbəti $m$ sətirin hər biri iki tam ədəd $c_i$ və $d_i$ ($1\le c_i\le n$, $1\le d_i\le 10^9$) ehtiva edir - $i$-ci bayramın keçiriləcəyi şəhərin nömrəsi və günün nömrəsi.

Çıxış formatı

Bir ədəd çıxarın - Kazak Vuhun iştirak edə biləcəyi maksimum bayramların sayı.

Qeyd

Əvvəlcə Kazak Vuh şəhər $3$-ə gələ bilər və bayramı gözləmək üçün bir gün gözləyə bilər. Daha sonra, birinci gün o, iki gün ərzində şəhər $1$-ə keçə bilər, burada üçüncü gün bayram olacaq. Eyni şəkildə, üçüncü gün o, şəhər $2$-yə gedə bilər, burada dördüncü gün də bayram olacaq. Lakin son bayrama çatmaq üçün artıq vaxtı çatmayacaq, çünki şəhər $4$-ə çatmaq üçün $3$ gün lazımdır. Beləliklə, o, $3$ bayramda iştirak etdi.

Nümunələr