خانم دکتر در پارک گم‌ شده‌ و آقای مهندس در حال گشتن پارک برای پیدا کردن اوست. می‌دانیم که در پارک $n$ تقاطع وجود دارد که با $n − 1$ گذرگاه به هم وصل شده‌اند، به طوری که می‌توان از هر تقاطعی به هر تقاطع دیگر رسید. (گراف جاده‌های پارک به شکل یک درخت است) خانم دکتر در تقاطع $e$ نشسته‌است و آقای مهندس که در تقاطع $s$ قرار دارد، می‌خواهد او را پیدا کند.

آقای مهندس که اولین‌بار است به این پارک آمده‌ و هیچ‌کجای آن را نمی‌شناسد، به هر تقاطعی که می‌رسد یکی از گذرگاه‌های متصل به آن را به صورت تصادفی و با احتمال برابر انتخاب کرده و آن را طی‌ می‌کند. طی‌کردن هر گذرگاه نیز مدت زمان مشخصی طول می‌کشد. او آن‌قدر این کار را انجام می‌دهد تا به تقاطع $e$ برسد و خانم دکتر را پیدا کند.

برنامه‌ای بنویسید که با گرفتن سناریو‌های مختلف مکان $s$ و $e$، امید ریاضی زمانی را که طول می‌کشد تا آقای مهندس خانم دکتر را پیدا کند، بیاید.

• سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد تقاطع‌ها و $q$، تعداد سناریو‌ها است.
• در هر کدام از $n − 1$ سطر بعد، سه عدد طبیعی $u$ و $v$ و $t$ آمده است که به معنای وجود یک گذرگاه بین دو تقاطع $u$ و $v$ است که $t$ دقیقه زمان برای عبور از آن لازم است.
• سپس در هر کدام از $q$ سطر بعدی دو عدد $s$، محل شروع حرکت آقای مهندس و $e$، تقاطعی که خانم دکتر در آن نشسته‌، آمده است.
• $1 \leq n, q \leq 10^5$
• $(u \neq v) 1 \leq u, v \leq n$
• $1 \leq t \leq 1000$
• $1 \leq s, e \leq n$

در $q$ سطر خروجی در هر سطر آن به ازای یک سناریو، امید ریاضی زمانی که طول می‌کشد تا آقای مهندس خانم دکتر را پیدا کند را چاپ کنید. اگر خطای نسبی پاسخ شما و پاسخ اصلی شما کمتر از $10^{-7}$ باشد، جواب شما پذیرفته خواهد شد.

• زیرمسئله اول (۱۰ نمره): $n \leq 10$
• زیرمسئله دوم (۲۰ نمره): $n \leq 1000$
• زیرمسئله سوم (۷۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد