- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کاپعلی یک جهان‌گرد است که می‌خواهد کشور کدکاپ را ببیند. لذت بردن از مسیر برای کاپعلی خیلی مهم است، بنابراین کاپعلی می‌خواهد تمام جاده‌هایی که می‌بیند برای او جدید باشند. به زبانی دیگر اگر در مسیرش جاده‌ای باشد که او قبلا از آن عبور کرده باشد، کاپعلی بسیار ناراحت می‌شود.
کاپعلی می‌خواهد سه شهر $v$، $u$ و $w$ را انتخاب کند و با شروع از $u$ ابتدا به $v$ برود و سپس از $v$ به $w$ برود و در طول این سفر هیچ‌گاه به دلیل دیدن جاده‌ی تکراری، ناراحت نشود. کاپعلی چند حالت برای انتخاب $v$، $u$ و $w$ دارد؟
ورودی
در سطر اول ورودی، ابتدا $n$، تعداد شهر‌های کدکاپ و سپس $m$، تعداد جاده‌های کدکاپ آمده است.
$$3 \leq n \leq 100 , 000$$ $$1 \leq m \leq 200 , 000$$
در $m$ سطر بعدی، در هر سطر دو عدد $b$ و $a$ آمده که یک جاده را نشان می‌دهد و مشخص می‌کند که این جاده شهر $a$ و $b$ را به هم متصل می‌کند.
$$1 \leq a,b \leq n$$
تضمین می‌شود هیچ جاده‌ای یک شهر را به خودش متصل نمی‌کند و بین هر دو شهر حداکثر یک جاده وجود دارد. توجه کنید که ممکن است از شهری در کدکاپ نتوان به شهری دیگر با استفاده از جاده‌ها رفت.
خروجی
در تنها سطر خروجی تعداد ($v$، $u$،$w$) هایی را چاپ کنید که کاپعلی می‌تواند از $u$ به $v$ و سپس به $w$ برود و در این میان هیچ جاده‌ای را بیش از یک بار نبیند.
مثال‌ها
ورودی نمونه ۱
3 3
1 2
2 3
1 3
خروجی نمونه ۱
6
ورودی نمونه ۲
7 5
1 2
2 3
3 4
4 5
6 7
خروجی نمونه ۲
20
ورودی نمونه ۳
7 6
1 2
1 3
2 4
2 5
3 6
3 7
خروجی نمونه ۳
54
ارسال پاسخ برای این سؤال