• محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • منبع: آزمون نهایی اول دوره ۲۶ المپیاد کامپیوتر

یک گراف ساده‌ی همبند nn راسی به شما داده است. در ابتدا رنگ تمامی راس‌ها به جز دو راس rr و bb، سفید است. راس rr قرمز رنگ است و یک مهره‌ی قرمز نیز روی آن وجود دارد. راس bb سیاه رنگ است و یک مهره‌ی سیاه روی آن وجود دارد.

در هر ثانیه به صورت تصادفی یکی از دو رنگ سیاه و قرمز انتخاب می‌شود و به ازای هر مهره از رنگ انتخاب شده، که برای مثال در راس vv قرار دارد، در تمامی راس‌های همسایه راس vv در گراف یک مهره‌ی جدید از همان رنگ قرار داده می‌شود. اگر راسی که مهره‌ی جدید در آن قرار می‌گیرد سفید باشد، رنگ راس به رنگ آن مهره‌ در خواهد آمد و در غیراین‌صورت رنگ راس تغییر نخواهد کرد.

راس‌های گراف در انتهای این عملیات، یعنی زمانی که تمامی راس‌ها رنگ شده‌اند، چند رنگ‌آمیزی متفاوت می‌توانند داشته باشند؟ دو رنگ ‌آمیزی متفاوت اند اگر رنگ یک راس در آن دو رنگ‌آمیزی متفاوت باشد.

ورودی

در خط اول ورودی چهار عدد طبیعی nn و mm و rr و bb، به ترتیب تعداد راس‌های گراف، تعداد یال‌های گراف، شماره‌ی راس rr و شماره‌ی راس bb، آمده است. در هر یک از mm خط بعدی دو عدد طبیعی viv_i و uiu_i آمده‌است که نشان‌دهنده‌ی وجود یک یال بین دو راس viv_i و uiu_i در گراف است. گراف داده شده ساده و همبند است. 2n100 0002 \le n \le 100\ 000 1mmin((n2),200 000)1 \le m \le min(\binom{n}{2}, 200\ 000) 1r,bn1 \le r, b \le n rbr \ne b 1vi,uin1 \le v_i, u_i \le n

خروجی

در تنها خط خروجی باقی‌مانده‌ی تعداد رنگ‌آمیزی‌های متفاوت گراف در انتهای عملیات بر 109+710^9+7 را چاپ کنید.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۱۷ n20n \le 20
۲ ۲۶ n1 000n \le 1\ 000
۳ ۵۷ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 3 2 3
1 2
2 3
3 4
Plain text

خروجی نمونه ۱

3
Plain text

ورودی نمونه ۲

6 6 1 6
1 2
2 3
2 4
3 5
4 5
5 6
Plain text

خروجی نمونه ۲

4
Plain text

ورودی نمونه ۳

8 9 1 2
1 3
3 2
1 4
4 5
5 2
1 6
6 7
7 8
8 2
Plain text

خروجی نمونه ۳

8
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.