- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک گراف ساده و همبند \(n\) راسی و \(m\) یالی داریم. میخواهیم روی هر راس این گراف یک عدد از مجموعه \(\{ 1, 2, 3, \dots, k\}\) بنویسیم.
اگر عدد نوشته شده روی راس \(v\) را با \(a_v\) و طول کوتاه ترین مسیر بین دو راس \(u\) و \(v\) را با \(dist(u, v)\) نشان دهیم.
میخواهیم این عدد گذاری به گونهای انجام شود که برای هر دو راس از این گراف مثل \(u\) و \(v\) داشته باشیم.
\[dist(u, v) = |a_u - a_v|\]
از شما میخواهیم تعداد روشهای انجام این کار را مشخص کنید. از آنجایی که پاسخ مسئله میتواند خیلی بزرگ باشد باقیمانده پاسخ مسئله را بر \(10^9 + 7\) را چاپ کنید.
ورودی
خط اول ورودی به ترتیب سه عدد \(n\) و \(m\) و \(k\) با فاصله از هم آمدهاند.
\[1 \le n \le 100\ 000\] \[n - 1 \leq m \leq min(\frac{n(n - 1)}{2},100 \, 000)\] \[1 \le k \le 10^9\]
در \(m\) خط بعدی و در هر خط دو عدد \(v\) و \(u\) با فاصله از هم آمدهاند که نشاندهندهی یالی بین دو رأس \(v\) و \(u\) هستند. \[1 \le v, u \le n\]
تضمین میشود گراف ورودی، گرافی ساده و همبند است.
خروجی
مثال
ورودی نمونه ۱
2 1 3
1 2
خروجی نمونه ۱
4
اگر عدد نوشته شده روی راس شماره \(v\) را با \(c(v)\) نشان دهیم؛ ۴ روش زیر برای این عدد گذاری وجود دارد.
- \(c(1) = 1, c(2) = 2\)
- \(c(1) = 2, c(2) = 1\)
- \(c(1) = 3, c(2) = 2\)
- \(c(1) = 2, c(2) = 3\)
ورودی نمونه ۲
3 3 2
1 2
2 3
3 1
خروجی نمونه ۲
0
در گراف بالا هیچ عدد گذاری قابل قبولی وجود ندارد، چون به ازای هر عددگذاری حداقل دو راس مجاور وجود دارد که عدد نوشته شده روی آنها یکسان خواهند داشت و این با خواسته سوال تناقض دارد.
ارسال پاسخ برای این سؤال