+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک گراف ساده‌ی همبند $n$ راسی به شما داده است. در ابتدا رنگ تمامی راس‌ها به جز دو راس $r$ و $b$، سفید است. راس $r$ قرمز رنگ است و یک مهره‌ی قرمز نیز روی آن وجود دارد. راس $b$ سیاه رنگ است و یک مهره‌ی سیاه روی آن وجود دارد. در هر ثانیه به صورت تصادفی یکی از دو رنگ سیاه و قرمز انتخاب می‌شود و به ازای هر مهره از رنگ انتخاب شده، که برای مثال در راس $v$ قرار دارد، در تمامی راس‌های همسایه راس $v$ در گراف یک مهره‌ی جدید از همان رنگ قرار داده می‌شود. اگر راسی که مهره‌ی جدید در آن قرار می‌گیرد سفید باشد، رنگ راس به رنگ آن مهره‌ در خواهد آمد و در غیراین‌صورت رنگ راس تغییر نخواهد کرد. راس‌های گراف در انتهای این عملیات، یعنی زمانی که تمامی راس‌ها رنگ شده‌اند، چند رنگ‌آمیزی متفاوت می‌توانند داشته باشند؟ دو رنگ ‌آمیزی متفاوت اند اگر رنگ یک راس در آن دو رنگ‌آمیزی متفاوت باشد. # ورودی در خط اول ورودی چهار عدد طبیعی $n$ و $m$ و $r$ و $b$، به ترتیب تعداد راس‌های گراف، تعداد یال‌های گراف، شماره‌ی راس $r$ و شماره‌ی راس $b$، آمده است. در هر یک از $m$ خط بعدی دو عدد طبیعی $v_i$ و $u_i$ آمده‌است که نشان‌دهنده‌ی وجود یک یال بین دو راس $v_i$ و $u_i$ در گراف است. گراف داده شده ساده و همبند است. $$2 \le n \le 100\ 000$$ $$1 \le m \le min(\binom{n}{2}, 200\ 000)$$ $$1 \le r, b \le n$$ $$r \ne b$$ $$1 \le v_i, u_i \le n$$ # خروجی در تنها خط خروجی باقی‌مانده‌ی تعداد رنگ‌آمیزی‌های متفاوت گراف در انتهای عملیات بر $10^9+7$ را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۷ | $n \le 20$ | | ۲ | ۲۶ | $n \le 1\ 000$ | | ۳ | ۵۷ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 3 2 3 1 2 2 3 3 4 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 6 6 1 6 1 2 2 3 2 4 3 5 4 5 5 6 ``` ## خروجی نمونه ۲ ``` 4 ``` ## ورودی نمونه ۳ ``` 8 9 1 2 1 3 3 2 1 4 4 5 5 2 1 6 6 7 7 8 8 2 ``` ## خروجی نمونه ۳ ``` 8 ```

حل سؤال در بانک سؤالات