گراف افکار


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

بعد از بیش از دو سال انتظار و جستجو برای هم تیمی، ابواسحاق متوجه شد کدکاپ ۵ انفرادی برگزار می‌شود! برای همین کلی ناراحت شد و رشته افکارش تبدیل به گراف شد! اکنون برای باز گرداندن آن به حالت عادی، دست به دامن شما شده است.

رشته افکار ابواسحاق یک گرافِ سادهٔ همبند nn راسی و mm یالی است. او تصمیم دارد برای بازگرداندن رشته افکارش در طی kk مرحله، هر مرحله یک یال به آن اضافه کند به طوری که گراف حاصل، ساده باقی بماند و دارای حداقل یک دور به طول فرد باشد. (گراف ساده گرافی است که دارای یال چندگانه و طوقه نباشد)

امّا او که سلامت روانش بسیار برایش مهم است، قبل از این که دست به کار شود از شما می‌خواهد تا تعداد روش‌های مختلف انجام این عمل را به او بگویید. از آنجا که تعداد حالات، ممکن است بسیار زیاد باشد، باقی ماندهٔ تقسیم آن بر 109+710^{9} + 7 را به او بگویید (دو روش از انجام kk مرحله را متمایز گوییم، اگر مرحله‌ای مثل ii وجود داشته باشد که دو سر یال اضافه شده در روش اول برابر با دو سر یال اضافه شده در روش دوم نباشد).

دقت کنید که ترتیب اضافه کردن kk یال اهمیت دارد.

ورودی🔗

در خط اول ورودی سه عدد nn، mm و kk آمده است.
در mm خط بعدی دو عدد vv و uu آمده است، که نشان می‌دهد یک یال بین رئوس vv و uu وجود دارد.

3n1 0003 \le n \le 1\ 000 n1m<(n2)n-1 \le m < {n \choose 2} 1v,un1 \le v, u \le n m+k(n2)m + k \le {n \choose 2} 1k1 \le k

تضمین می‌شود گراف ورودی، گرافی همبند و ساده است.

خروجی🔗

در خروجی باید باقی‌مانده تعداد روش‌های خواسته شده بر 109+710^{9} + 7 را چاپ کنید.

ورودی نمونه ۱🔗

4 3 2
1 2
2 3
3 4
Plain text

خروجی نمونه ۱🔗

6
Plain text
توضیحات مثال

حالت های معتبر به شکل زیر هستند: (1,3),(1,4){(1, 3), (1, 4)} (1,3),(2,4){(1, 3), (2, 4)} (1,4),(2,4){(1, 4), (2, 4)} (1,4),(1,3){(1, 4), (1, 3)} (2,4),(1,3){(2, 4), (1, 3)} (2,4),(1,4){(2, 4), (1, 4)} هر سطر نشان دهندهٔ یک حالت از انجام kk مرحله است. ((i,j)(i, j) نمایانگر کشیدن یال بین دو رأس ii و jj است و یال‌ها را در هر سطر از چپ به راست اضافه می‌کنیم)

ورودی نمونه ۲🔗

3 2 1
1 2
1 3
Plain text

خروجی نمونه ۲🔗

1
Plain text

تنها می‌توان یال (2,3)(2, 3) را اضافه کرد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.