گراف شکننده (Fragile Graph)

کریستف کلمب، دریانورد مشهور ایتالیایی، در یکی از سفرهای خود با گراف وزن‌دار جادویی آشنا شد. پس از پرس‌وجوهای بسیار، کریستف متوجه شد که گراف‌ وزن‌دار جادویی در محل زندگی‌اش طرفداران زیادی دارد و می‌تواند آن‌ را به قیمت بالایی بفروشد تا از این راه بتواند قسط این ماه کشتی‌اش را پرداخت کند!

پس از بررسی بیشتر، کریستف متوجه شد که ارزش گراف ‌وزن‌دار جادویی برابر کمینه درخت فراگیر آن یا همان mst این گراف است (اگر گراف ناهمبند باشد ارزش آن ۰ است). اما جابه‌جایی گراف وزن‌دار جادویی کار راحتی نیست، در طی مسیر برگشت به خانه، یال ‌$i$ام این گراف به احتمال ‌$p_i$ می‌شکند و از گراف حذف می‌شود. کریستف که نگران قسط‌هایش است، می‌خواهد بداند که هنگامی که به خانه می‌رسد، امید ‌ریاضی ارزش گراف وزن‌دار جادویی چند است؟

در خط اول، ۲ عدد $n$ و $m$ می‌آیند که به ترتیب نمایانگر تعداد رئوس و یال های گراف‌ وزن‌دار جادویی هستند.

در هر یک از $m$ خط بعدی، ۴ عدد $u_i$، $v_i$، $w_i$ و $p_i$ آمده که ۳ عدد اول به ترتیب برابر دو سر یال $i$ام و وزن یال $i$ام است. همچنین احتمال شکستن یال $i$ام برابر $\frac{p_i}{10^8}$ است.

در تنها خط خروجی جواب مسئله را به پیمانه $998244353$ خروجی دهید.

• زیرمسئله اول (۶ نمره): گراف ورودی دور است.
• زیرمسئله دوم (۴ نمره): $m \leq 18$.
• زیرمسئله سوم (۱۵ نمره): $n \leq 10$.
• زیرمسئله چهارم (۱۴ نمره): $n = 15, m = 25$.
• زیرمسئله پنجم (۱۷ نمره): $w_i = 1$.
• زیرمسئله ششم (۲۱ نمره): $n \leq 13$.
• زیرمسئله هفتم (۲۳ نمره): بدون محدودیت اضافی.

• $1 \leq n \leq 15$
• $1 \leq m \leq min(\binom{n}{2},\,40)$
• $1 \le v_i, u_i \le n$
• $1 \le w_i \le 10^9$
• $0 < p_i < 10^8$
• یال چندگانه و طوقه وجود ندارند.
• گراف ورودی همبند است.

3 3
1 3 3 50000000
2 3 4 25000000
1 2 2 25000000

779878405

5 9
1 4 1 50000000
3 5 1 50000000
1 5 1 50000000
1 2 1 50000000
2 3 1 50000000
2 4 1 50000000
1 3 1 50000000
4 5 1 50000000
3 4 1 50000000

545914883

5 9
1 4 975760966 41771707
1 5 287816499 94176294
4 5 669890473 56500675
2 4 192335765 76968324
3 4 135887322 57538763
2 3 477909655 65101098
3 5 742307822 11702335
2 5 238536537 36133290
1 2 494132950 17978224

543882524

در ورودی اول، یال اول به احتمال $\frac{1}{2}$ و دو‌‌ یال دیگر هر یک به احتمال $\frac{1}{4}$ می‌شکنند. میتوان دید که به احتمال $\frac{1}{2} \times \frac{3}{4} \times \frac{3}{4} = \frac{9}{32}$ هیچ یک از یال ها نمی‌شکنند و MST گراف برابر ۵ خواهد شد. از طرفی دیگر، به احتمال $\frac{1}{2} \times \frac{3}{4} \times \frac{3}{4} = \frac{9}{32}$ تنها یال اول، به احتمال $\frac{1}{2} \times \frac{1}{4} \times \frac{3}{4} = \frac{3}{32}$ تنها یال دوم و به احتمال مشابه تنها یال سوم می‌شکند که به ترتیب MST گراف در این حالات برابر ۶،‌ ۵ و ۷ خواهد شد. از طرفی دیگر اگر بیش از یک یال بشکند، گراف ناهمبند شده و ارزشش ۰ می‌شود، در نتیجه امید‌ریاضی ارزش گراف برابر $\frac{9}{32} \times 5 +‌ \frac{9}{32} \times 6 + \frac{3}{32} \times 5 +‌ \frac{3}{32} \times 7 = \frac{135}{32}$ خواهد‌ شد که به پیمانه گفته شده برابر 779878405 می‌شود.