أنشأ 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$ التالية الأزواج المقارنة يدويًا. يحتوي كل سطر على ثلاثة أعداد صحيحة $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$ التالية أسئلة Farmer John وعددها $Q$. يحتوي كل سطر على عددين صحيحين $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$ اطبع جواب سؤال FJ رقم $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$.

يريد Farmer John معرفة عدد الاقتراحات من الفيديو2 إذا $K=1$، ومن الفيديو1 إذا $K=3$، ومن الفيديو1 إذا $K=4$. عند $K=1$ تقترح الفيديوهات1 و3 و4 في الفيديو2. وعند $K=4$ لا يقترح شيء من الفيديو1. وعند $K=3$ يقترح الفيديوهان2 و4 من الفيديو1.

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