- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
گرچه آقا فیروز در تپ‌نپ خیلی اذیت شد ولی توانست پول خوبی به دست آورد. او تصمیم گرفت با این پول یک بازی فکری برای بچه‌هایش بخرد تا هوش ریاضی آن‌ها را پرورش دهد.
وقتی آقا فیروز بازی را به پسرش علی داد، او خیلی خوشحال شد و سریع شروع به بازی کرد. بازی از یک صفحه تشکیل شده بود که روی آن دو عدد $n$ و $m$ نوشته شده بود و در زیر آن $n$ نقطه کشیده شده بود که $m$ جفت از آن‌ها با پاره‌خط‌هایی به‌صورت خط‌چین به هم وصل شده بودند.
علی باید طوری پاره‌خط‌ها را با رنگ‌های ۱ و ۲ و ۳ رنگ‌آمیزی می‌کرد که در انتها هر پاره‌خطی که رنگ ۱ دارد، حتما حداقل یک پاره‌خط مجاور با رنگ ۲ داشته باشد. دو پاره‌خط مجاور هستند اگر یک سر آن‌ها مشترک باشد.
علی که از راحتی این بازی جا خورده بود، تصمیم گرفت تا هوش ریاضی خود را به پدرش ثابت کند و تعداد روشهای رنگ‌آمیزی صفحه با شرایط را به دست آورد. او که در ابتدا متوجه سختی مسئله نبود، پس از مدتی فکر کردن و ناتوانی در حل آن خیلی ناراحت شد.
حال برای این که علی ناراحت نشود شما تعداد روشهای رنگ‌آمیزی را به دست آورید و به او بگویید.
همچنین به‌دلیل اینکه ممکن است خروجی بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ چاپ کنید.
ورودی
در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب تعداد نقاط و پاره‌خط‌ها را نشان می‌دهد.
در $i$امین خط از $m$ خط بعدی دو عدد $v_i$ و $u_i$ آمده است که نشان‌دهنده وجود پاره‌خطی بین دو نقطه با شماره $v_i$ و $u_i$ می‌باشد. تضمین می‌شود همواره $v_i$ و $u_i$ متفاوت هستند و بین هر جفتی حداکثر یک پاره‌خط قرار دارد. $$1 \le n \le 18$$ $$1 \le m \le \frac{n \times (n - 1)}{2}$$ $$1 \le v_i, u_i \le n$$
خروجی
در تنها خط خروجی، تعداد روشهای رنگ‌آمیزی پاره‌خط‌ها را به باقیمانده $10^9 + 7$ به دست آورید به‌طوری که شرایط بازی رعایت شود.
مثال
ورودی نمونه ۱
4 2
1 2
3 4
خروجی نمونه ۱
4
ورودی نمونه ۲
3 3
1 2
2 3
3 1
خروجی نمونه ۲
20
ارسال پاسخ برای این سؤال