في وقت فراغه أنشأ Farmer John خدمة مشاركة الفيديو MooTube. تستطيع أبقاره تسجيل ومشاركة واكتشاف فيديوهات ممتعة. نشرت $N$ فيديو ($1\le N\le100{,}000$) مرقمة $1\ldots N$، لكنه لا يعرف كيف يساعدها على العثور على فيديوهات جديدة تعجبها.

يريد قائمة «فيديوهات مقترحة» لكل فيديو، توصي بالأكثر ارتباطًا بما تشاهده الأبقار بالفعل.

ابتكر FJ «درجة ارتباط» بين الفيديوهات. اختار $N-1$ زوجًا وحسب ارتباط كل زوج يدويًا. يمثل الفيديوهات كرؤوس شبكة ويربط الأزواج المختارة بحيث يوجد مسار واحد بالضبط بين أي فيديوهين. يُعرّف ارتباطهما بأنه أصغر ارتباط لأي وصلة في هذا المسار.

يريد FJ اختيار $K$ ليقترح بجانب كل فيديو كل الفيديوهات الأخرى ذات ارتباط لا يقل عن $K$. لكن كثرة المقترحات قد تشغل الأبقار عن إنتاج الحليب! لذا يريد اختيار $K$ بعناية ويطلب إجابات عن المقترحات لقيم معينة من $K$.

الإدخال

السطر الأول يحوي $N,Q$ ($1\le Q\le100{,}000$).

الأسطر $N-1$ التالية تصف الأزواج المقارنة يدويًا. الأعداد الصحيحة $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) تعني وصلة بين $p_i,q_i$ بارتباط $r_i$.

الأسطر $Q$ التالية تصف الأسئلة. العددان الصحيحان $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) يسألان في السؤال $i$ عن عدد الفيديوهات المقترحة لمشاهدي $v_i$ إذا $K=k_i$.

الإخراج

اطبع $Q$ سطرًا؛ السطر $i$ إجابة السؤال $i$.

أمثلة

الإدخال 1

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

الإخراج 1

3
0
2

ملاحظة

ارتباط $1,2$ هو $3$ و$2,3$ هو $2$ و$2,4$ هو $4$. إذن ارتباط $1,3$ هو $\min(3,2)=2$ و$1,4$ هو $\min(3,4)=3$ و$3,4$ هو $\min(2,4)=2$.

يسأل FJ عن الفيديو $2$ عند $K=1$ وعن $1$ عند $K=3$ وعن $1$ عند $K=4$. عند $K=1$ يقترح $2$ الفيديوهات $1,3,4$، وعند $K=4$ لا يقترح $1$ شيئًا، وعند $K=3$ يقترح $1$ الفيديوهين $2,4$.

مؤلف المسألة: Jay Leeds