+ محدودیت ز مان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بدخواه، بدِ هالو را میخواهد. او میخواهد هالو را به سفر دور کشور ببرد و به ازای هر دور پول بگیرد و اینقدر دور کشور بچرخاند تا هالو سرش گیج برود!!(سر خود بدخواه هم گیج می‌رود ولی همین که سر هالو گیج برود احساس رضایتی به بد‌خواه میدهد که سرگیجه در مقابلش هیچ است) کشور بدخواه و هالو $n$ شهر دارد. بدخواه و هالو در شهر ۱ هستند. بدخواه و هالو اینگونه دور کشور میگردند: در هر بار گردش از شهر ۱ شروع کرده، تمام شهر های کشور به غیر از شهر ۱ را دیده و به شهر ۱ برمیگردند.هر گردش به دور کشور $n$ روز طول میکشد. در هر روز (غیر از روز $n$ ام) آنها یک شهر جدید را که قبلا ندیده بودند، خواهند دید و در روز $n$ ام آنها به شهر اول برمیگردند. به عبارت دیگر هر گردش میشود یک دور که دارای تمام شهر های کشور باشد(دور همیلتونی). برای اینکه آنها از یک شهر به شهر دیگر بروند، باید از جاده‌ی بین این دو شهر استفاده کنند. بین هر دو شهری جاده وجود دارد اما متاسفانه در $k$ تا از جاده ها پلیس وجود دارد که اگر از آن جاده‌ها رد شوند، پلیس بدخواه را به جرم بدخواهی شناسایی و دستگیر میکند. بنابراین بدخواه نمیخواهد که از آن جاده‌ها عبور کنند. نکته ای که وجود دارد این است که هیچ دو گردشی نباید مثل هم باشند؛ یعنی ترتیب دیدن شهر ها در هر دو گردشِ متفاوت، باید متفاوت باشد؛ وگرنه هالو متوجه این میشود که دارند به دور خود میچرخند و سرش را با دست محکم نگه میدارد و دیگر سرش گیج نمیرود و تازه، نامرد دیگر پول هم نمیدهد!! **اگر یکی از گردش ها دقیقاً برعکس دیگری باشد نیز هالو متوجه میشود و چنین اتفاقی می‌افتد.** حالا بدخواه میخواهد بداند که هالو را حداکثر به چند گردش متفاوت میتواند ببرد تا هم سرگیجه‌ی هالو به بیشترین مقدار خود برسد و هم بدخواه بداند که حداکثر چقد پول گیرش می‌آید و هم اینکه بدخواه بتواند وقتش را برای بدخواهی بعدی تنظیم نماید(نظم، کلید موفقیت است)!! اما چون امکان دارد تعداد دور‌های متفاوت زیاد باشد، بدخواه باقیمانده‌ی این عدد را بر $9901$ از شما میخواهد. # ورودی در سطر اول ورودی به ترتیب دو عدد $n$ و $k$ آمده است که به ترتیب نشان‌دهنده ی تعداد شهر‌های کشور و تعداد جاده‌هایی است که در آنها پلیس وجود دارد. سپس در $k$ سطر بعدی، در هر سطر، $u_i$ و $v_i$ آمده‌است که نمایانگر شماره‌ی شهر‌هایی است که جاده‌ی بین آنها دارای پلیس است. (یعنی هالو و بدخواه نمیتوانند در طول گردش از شهر با شماره‌ی $u_i$ به $v_i$ و یا برعکس، سفر کنند.) میتوانید فرض کنید که هر جاده حداکثر یک بار در ورودی ظاهر میشود. $$ v_i \neq u_i$$ $$ 3 \le n \le 300 $$ $$ 1 \le v_i, u_i \le n $$ $$ 0 \le k \le 15 $$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که باقیمانده‌ی حداکثر تعداد دورهایی که بدخواه میتواند هالو را دور کشور بچرخاند، بر $9901$ است. # مثال ## ورودی نمونه ۱ ``` 4 1 1 2 ``` ## خروجی نمونه ۱ ``` 1 ``` توضیح: تنها دوری که وجود دارد، 1-3-2-4 است. ## ورودی نمونه ۲ ``` 8 4 1 2 2 3 4 5 5 6 ``` ## خروجی نمونه ۲ ``` 660 ```