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

اخیرا اساتید مدرسه‌ی جادوگری هاگوارتز نام «امیرمحمّد ایمانی» زیاد به گوششان خورده و به دامبلدور، مدیر مدرسه، پیشنهاد می‌دهند که برای امیرمحمّد دعوت‌نامه‌ای بفرستد تا امیرمحمّد بتواند در این مدرسه ادامه تحصیل دهد. دامبلدور دستی به محاسنش می‌کشد و می‌گوید: «باشه بهش می‌گم...».

سپس با یک سوت بلبلی جغدش را صدا می‌زند و دعوت‌نامه‌ی امیرمحمّد را با جغدش برای او می‌فرستد. امیرمحمّد ابتدا از دیدن جغد شوکه می‌شود و شروع به جیغ کشیدن و فرار کردن می‌کند. جغد اعصابش خرد می‌شود و فریاد می‌زند: «بسه باو کر شدیم. بیا دعوت‌نامه‌تو بگیر این جا رم امضا کن ما بریم پی کارمون. :/»

امیرمحمّد دعوت‌نامه را امضا می‌کند و مشغول تحصیل می‌شود. پس از چندین ماه تحصیل و تمرین و ممارست، حسابی در جادوگری پیشرفت می‌کند و به درجات بالای علمی می‌رسد. یک روز که او داشت برای خودش در جنگل کنار مدرسه قدم می‌زد، آقا گرگه جلوی او را می‌گیرد و می‌گوید: «بیا بخورمت.». امیرمحمّد می‌گوید: «بیی‌خیال... بذار برم غذا بخورم چاااق بشم... چلّه بشم... بعد می‌آم تو منو بخور.» خلاصه از آقا گرگه اصرار و از امیرمحمّد انکار...

تا این که آقا گرگه خسته می‌شود و $n$ درخت $n$ راسی که دقیقا مشابه یکدیگر هستند را به امیرمحمّد نشان می‌دهد و می‌گوید: «اصلا مگه تو جادوگر نیستی؟ بیا این $n$ تا درخت رو برام غیب کن!» امیرمحمّد بادی در غبغب می‌اندازد و می‌گوید: «بله که هستم! بذار الآن غیبشون می‌کنم!».

او می‌خواهد درخت‌ها را به ترتیب غیب کند. یعنی اوّل درخت اوّل، سپس درخت دوم و... طلسمی که امیرمحمّد برای این کار بلد است، ابتدا دارای قدرت $n$ است. امّا هر بار که امیر محمّد یک درخت را به طور کامل غیب می‌کند، یک واحد از قدرتش کاسته می‌شود. یعنی پس از غیب کردن تمام درخت‌ها قدرت طلسم به $0$ می‌رسد.

این طلسم به این شکل عمل می‌کند که هر بار امیرمحمّد یکی از رئوس درخت(مثل $v$) را نشانه می‌گیرد و با اعمال آن طلسم، تمام رئوس در زیردرخت $v$ که فاصله‌شان از $v$ حداکثر به اندازه‌ی قدرت آن طلسم است، غیب می‌شوند. (راس $v$ می‌تواند از قبل غیب شده باشد)

برای امیرمحمّد برنامه‌ای بنویسید که بگوید برای غیب کردن تمامی این $n$ درخت $n$ راسی چند بار باید از طلسمش استفاده کند.

نکته: این درخت‌ها ریشه‌دار هستند. یعنی راس $u$ در زیردرخت راس $v$ قرار دارد اگر و فقط اگر در مسیر ریشه به $u$، راس $v$ ظاهر شود. هم‌چنین ریشه‌ی تمام این درخت‌ها راس $1$ است.

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است.
در هر یک از $n - 1$ سطر بعد دو عدد آمده است که نشان‌دهنده‌ی اعداد دو سر هر یال هستند. تضمین می‌شود یال‌هایی که در ورودی داده می‌شود تشکیل یک درخت می‌دهند.

• $1 \le n \le 10^{5}$
• $1\le$ اعداد دو سر یال $\le n$

خروجی🔗

در تنها سطر خروجی، عددی که امیرمحمّد می‌خواهد را چاپ کنید.

زیر مسئله ها🔗

مثال🔗

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

4
1 2
2 3
2 4

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

5

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

6
1 2
1 3
1 4
4 5
4 6

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

7    

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

روح‌ا... پس از چندین سال تجربه در المپیاد، فهمید که «نون توی گله!»

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

باغچه‌ای که او اجاره کرد به شکل یک مستطیل $n$ در $m$ است. این مستطیل را به شکل جدولی در نظر بگیرید که $n$ سطر و $m$ ستون دارد و در هر خانه از آن جدول می‌توان یک گل کاشت. سطرهای جدول به ترتیب از بالا به پایین با $1$ تا $n$ و ستون‌های جدول از چپ به راست به ترتیب با $1$ تا $m$ شماره‌گذاری شده‌اند.

گل‌های مورد نظر روح‌ا... $26$ نوع دارند. هر یک از این انواع را با یکی از حروف $A$ تا $Z$ نمایش می‌دهیم. همچنین او می‌خواهد در سطر $i$ام باغچه‌اش گل‌هایی را بکارد که با رشته‌ای به نام $s_i$ نمایششان می‌دهیم. ممکن است طول این رشته از $m$ کم‌تر باشد. در این صورت او مجبور است تعدادی از خانه‌های باغچه را در آن سطر خالی بگذارد. برای او فقط ترتیب گل‌ها در هر سطر مهم است. یعنی اگر خانه‌های خالی سطر $i$ام را حذف کنیم و به ازای خانه‌های باقی‌مانده به ترتیب از چپ به راست نوعشان را بنویسیم، رشته‌ای برابر $s_i$ حاصل خواهد شد.

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

مثلا اگر یک جدول $2 \times 2$ داشته باشیم و $s_1 = s_2 = A$ باشد، اگر گل‌ها را در خانه‌ی اوّل سطر اوّل و خانه‌ی دوم سطر دوم بکاریم، شادابی برابر $0$ می‌شود. امّا اگر آن‌ها را در خانه‌های دوم دو سطر بکاریم، شادابی باغچه‌ی حاصل برابر $1$ می‌شود. همچنین اگر $s_1 = AA$ و $s_2 = BB$ باشد، روح‌ا... فقط به یک طریق می‌تواند گل‌ها را بکارد و شادابی حاصل نیز برابر $2$ خواهد بود.

روح‌ا... می‌خواهد طوری گل‌ها را بکارد که با شرایط مذکور، شادابی باغچه بیشینه شود. امّا او که از المپیاد کناره‌گیری کرده‌است، به نظرش این سوال خیلی المپیادی است و از شما می‌خواهد حلش کنید.

ورودی🔗

در سطر اوّل $2$ عدد $n$ و $m$ آمده‌اند.
در هر یک از $n$ سطر بعد، یک رشته‌‌ی ناتهی شامل حروف $A$ تا $Z$ آمده‌است که $i$امین رشته، نمایان‌گر $s_i$ است.

• $1 \le n \le 128$
• $1 \le m \le 16$
• $1 \le |s_i| \le m$

خروجی🔗

در تنها سطر خروجی، بیشینه شادابی ممکن باغچه را چاپ کنید.

زیر مسئله ها🔗

مثال🔗

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

1 1
B

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

0

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

2 12
A
B

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

0

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

3 3
B
AB
A

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

2

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

پس از برگزاری کلاس‌های دوره‌ی تابستانه‌ی المپیاد کامپیوتر، زمان برگزاری امتحانات نهایی عملی رسیده است.

در این دوره‌ی تابستانه $n$ دانش‌پژوه در حال دانش پژوهیدن بودند و بنابراین در امتحانات نهایی نیز $n$ دانش‌پژوه دانش خواهند پژوهید. در سالن برگزاری امتحانات نیز $n$ کامپیوتر برای آن‌ها آماده شده‌است که دور یک میز دایره‌ای قرار گرفته‌اند و به ترتیب ساعتگرد با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند.

امیرمحمّد که خیلی دوست داشت اثری از او در امتحانات نهایی هم موجود باشد، وظیفه‌ی خطیر مشخّص کردن جای نشستن دانش‌پژوهان در آزمون اوّل را برعهده گرفت. بنابراین به هر دانش‌پژوه یک عدد از $1$ تا $n$ نسبت داد که شماره‌ی کامپیوتر او را مشخّص می‌کرد. به عبارت دیگر یک آرایه‌ی $a$ به طول $n$ مشخّص کرد که $a_i$ شماره‌ی کامپیوتر دانش‌پژوه $i$ام در حین آزمون را مشخّص می‌کرد.

امّا قضیه به همین سادگی‌ها نبود... به دلیل پاره‌ای از مشکلات فنّی، آرایه‌ی $a$ شامل تعدادی عضو تکراری بود! یعنی به برخی از دانش‌پژوهان کامپیوتر یکسانی نسبت داده شده بود. امیرمحمّد که پیش از شروع امتحان متوجّه این ماجرا شده بود، مشکل را با مجید در میان گذاشت.

مجید تصمیم گرفت روند نشستن دانش پژوهان در سالن به این شکل باشد که ابتدا آن‌ها پشت در سالن امتحان در یک صف بایستند؛ سپس به ترتیب از ابتدای صف وارد سالن امتحان شوند. هر گاه دانش‌پژوهی وارد سالن امتحان شد و دید که دانش‌پژوهی پشت کامپیوتر مورد نظرش نشسته است، سراغ کامپیوتر بعدی(در جهت ساعتگرد) برود. دانش‌پژوه باید این کار را تا زمانی ادامه دهد که به یک کامپیوتر خالی برسد و پای آن کامپیوتر بنشیند. به عبارت دیگر دانش‌پژوه $i$ام پشت اوّلین کامپیوتر بعد از $a_i$(با احتساب خود $a_i$) می‌نشیند که در زمان وارد شدن او به سالن دانش‌پژوه دیگری پشتش ننشسته باشد. پس از آن که هر دانش‌پژوه پشت کامپیوتری نشست، نفر بعدی صف وارد سالن می‌شود.

به این ترتیب دانش‌پژوهان بدون مشکل خاصی توانستند پای کامپیوترهایشان بنشینند و آزمون با خوبی و خوشی برگزار شود. در حین برگزاری آزمون مجید ماجرای پیش آمده را برای شایان تعریف کرد. شایان که به شدّت از کمبود سوال برای امتحانات عملی رنج می‌برد، تصمیم گرفت از این ماجرا هم سوالی طرح کند! شایان آرایه‌ی $b$ به طول $n$ را تعریف کرد: $b_i$ شماره کامپیوتری است که دانش‌آموز $i$ام پشت آن نشسته است. سوال شایان این بود که اگر ما آرایه‌ی $a$ و $b$ را داشته باشیم، دانش‌پژوهان به چند طریق می‌توانند پشت در سالن امتحان صفی تشکیل دهند که پس از آن که وارد سالن شدند، که دانش‌آموز $i$ام پشت کامپیوتر $b_i$ نشسته باشد.

شایان که باید به آماده‌سازی سوالات دیگری بپردازد، از شما می‌خواهد این سوال را برای او حل کنید!

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است.
در $i$امین سطر بعد، به ترتیب دو عدد $a_i$ و $b_i$ آمده‌است.
تضمین می‌شود که آرایه‌ی $b$ یک جایگشت است.

• $1 \le n \le 10^{5}$
• $1 \le a_i, b_i \le n$

خروجی🔗

در تنها خط خروجی, باقی‌مانده‌ی تعداد ترتیب‌های معتبر را به پیمانه‌ی $10^9 + 7$ خروجی دهید.

زیر مسئله ها🔗

مثال🔗

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

3
2 2
3 3
2 1

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

2

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

13
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13

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

227020758

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

4
4 4
3 1
1 2
2 3

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

0