בזמנו הפנוי יצר Farmer John שירות חדש לשיתוף סרטונים בשם MooTube. פרותיו יכולות להקליט, לשתף ולגלות סרטונים משעשעים רבים. הן כבר העלו $N$ סרטונים ($1 \leq N \leq 5000$), ממוספרים $1 \ldots N$. אולם FJ אינו יודע כיצד לעזור להן למצוא סרטונים חדשים שימצאו חן בעיניהן.

FJ רוצה ליצור רשימת „סרטונים מומלצים” לכל סרטון ב־MooTube, כך שהפרות יקבלו המלצות לסרטונים הקשורים ביותר לאלה שהן כבר צופות בהם.

FJ מגדיר מדד „רלוונטיות”, המציין, כשמו, עד כמה שני סרטונים קשורים זה לזה. הוא בוחר $N-1$ זוגות ומחשב ידנית את הרלוונטיות שלהם. לאחר מכן הוא מציג את הסרטונים כרשת: כל סרטון הוא צומת, ו־$N-1$ הזוגות שנבדקו מחוברים. הוא בחר את $N-1$ הזוגות כך שבין כל שני סרטונים יש בדיוק מסלול חיבורים אחד. הרלוונטיות של כל זוג מוגדרת כרלוונטיות המזערית של חיבור במסלול זה.

Farmer John רוצה לבחור $K$ כך שליד כל סרטון ב־MooTube יומלצו כל הסרטונים האחרים שרלוונטיותם אליו היא לפחות $K$. אך הוא חושש שיותר מדי המלצות יסיחו את דעת הפרות מייצור חלב! לכן הוא רוצה לבחור $K$ מתאים בזהירות. עזרו לו לענות על שאלות בנוגע להמלצות עבור ערכי $K$ מסוימים.

קלט

השורה הראשונה מכילה $N$ ו־$Q$ ($1 \leq Q \leq 5000$).

$N-1$ השורות הבאות מתארות את הזוגות ש־FJ השווה ידנית. כל שורה מכילה שלושה שלמים $p_i$, $q_i$ ו־$r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$), המציינים שהסרטונים $p_i$ ו־$q_i$ מחוברים ברלוונטיות $r_i$.

$Q$ השורות הבאות מתארות את $Q$ השאלות של Farmer John. כל שורה מכילה שני שלמים $k_i$ ו־$v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): שאלה $i$ שואלת כמה סרטונים יומלצו לצופי הסרטון $v_i$ כאשר $K = k_i$.

פלט

הדפיסו $Q$ שורות. בשורה $i$ הדפיסו את התשובה לשאלה $i$ של FJ.

דוגמאות

קלט 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$.

Farmer John רוצה לדעת כמה סרטונים יומלצו מהסרטון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