+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... به تازگی پلیس با خبر شده که قرار است حمله‌ای تروریستی به شهر بشود. فعلا تروریست‌ها در خانه‌هایی در کنار خیابان آزادی پنهان شده‌اند. در کنار خیابان آزادی $n$ خانه وجود دارد و در هر خانه **حداکثر یک** تروریست زندگی می‌کند. برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، $m$ پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس $i$-ام خانه‌های $l_i$ تا $r_i$ را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند. مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید. # ورودی در سطر اوّل ورودی به ترتیب دو عدد $n$ و $m$ می‌آید. در سطر $i$-ام از $m$ سطر بعد، دو عدد $l_i$ و $r_i$ آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس $i$-ام زیر نظر گرفته است. $$1 \le l_i \le r_i \le n$$ $$1 \le n, m \le 100\ 000$$ # خروجی در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند. # مثال ## ورودی نمونه ۱ ``` 5 2 1 3 2 4 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 6 3 2 4 3 5 2 5 ``` ## خروجی نمونه ۲ ``` 3 ```

ترور

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

«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...

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

برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، $m$ پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس $i$ -ام خانه‌های $l_i$ تا $r_i$ را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند.

مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید.

ورودی🔗

در سطر اوّل ورودی به ترتیب دو عدد $n$ و $m$ می‌آید.

در سطر $i$ -ام از $m$ سطر بعد، دو عدد $l_i$ و $r_i$ آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس $i$ -ام زیر نظر گرفته است.

$1 \le l_i \le r_i \le n$ $1 \le n, m \le 100\ 000$

خروجی🔗

در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند.

مثال🔗

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

5 2
1 3
2 4

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... برای حل این بحران، مسریکس ماشین زمان میسیکس را قرض می‌گیرد و به عصر دایناسورها سفر می‌کند. او می‌داند که در آن زمان، نژادهای مختلفی از هر دایناسور وجود داشته است و خصوصیت مشترک دایناسورهای از هر نژاد، تعداد پاهای آن‌هاست! یعنی ممکن نیست دو دایناسور هم‌نژاد وجود داشته باشند که تعداد پاهایشان فرق داشته باشد. از آن جایی که اگر مسریکس حواسش نباشد ممکن است زیر پای کُرّه دایناسورها له شود، کنار یک بزرگ‌راه پنهان شده و به دایناسورهایی که از پل عابر پیاده‌ی بالای بزرگ‌راه رد می‌شوند نگاه می‌کند. البته چون یک بیلبورد تبلیغاتی جلوی پل عابر نصب شده است، مسریکس فقط می‌تواند از زیر بیلبورد، پاهای دایناسورها را ببیند. جالب است بدانید او می‌تواند از شکل پاهای دایناسورها، نژاد آن‌ها را بفهمد. مسریکس هر دسته پای متوالی که متعلّق به یک نژاد از دایناسورها باشد را ببیند، به شما تعداد و نژاد آن دسته پا را می‌گوید. اگر برای مدّت زیادی هیچ پایی از روی پل عابر عبور نکند، مسریکس به این نتیجه می‌رسد که هر دایناسور یا به طور کامل از روی پل رد شده است و یا هنوز هیچ کدام از پاهایش را روی پل نگذاشته است. در این حالت برای این که سکوت را بشکند از شما می‌پرسد که «تعداد پاهای نژادهای مختلف دایناسورها چند حالت می‌تونه داشته باشههه؟» مثلا اگر مسریکس بگوید که «۱ پا متعلّق به نژاد ۱ روی پل عابر دیدم، بعد ۴ پا متعلّق به نژاد ۲ روی پل عابر دیدم و بعد ۱ پا متعلّق به نژاد ۱ دیدم و برای مدّت زمان طولانی دیگه پایی از روی پل عابر رد نشد، بگو تعداد حالات پاهای دایناسورها چند تاست.» شما باید به او بگویید ۶. چرا که ممکن است دایناسورهایی که از نژاد ۱ هستند ۱ یا ۲ پا داشته باشند و دایناسورهایی که از نژاد ۲ هستند می‌توانند ۱، ۲ یا ۴ پا داشته باشند. و اگر بعد از آن به شما بگوید که «۳ پا متعلّق به دایناسور نژاد ۲ دیدم و برای مدّت طولانی کسی از روی پل رد نشد، دوباره بگو چند حالت دارههه.» شما باید بگویید ۲! چرا که دایناسورهای نژاد ۲ فقط ۱ پا می‌توانند داشته باشند. هم‌چنین مسریکس فرض می‌کند نژادهایی که تا به حال هیچ پایی از آن نوع از پل رد نشده است منقرض شده‌اند و شما نباید در شمارش تعداد حالات، به تعداد پاهای نژادهای مشاهده نشده اهمّیت بدهید. برای مثال اگر مسریکس پیش از آن که دایناسوری از پل عبور کند از شما تعداد حالات را بپرسد، شما باید در جواب عدد ۱ را بگویید. حواستان باشد که هنگامی که مسریکس دو مرتبه پاهای یک نژاد را می‌بیند، اگر بین این دو مرتبه هیچ پرسشی نکرده باشد، ممکن است همه پاهایی که در این دو مرتبه دیده متعلّق به یک دایناسور باشد اما اگر بین آن‌ها پرسشی انجام داده باشد، قطعا پاهای دایناسورهای مختلف بوده‌اند. مشاهدات مسریکس در ورودی آمده است. به ازای هر پرسش مسریکس، جواب آن پرسش را در خروجی چاپ کنید تا او بتواند جلوی گرمایش را بگیرد. فقط چون این مقدار ممکن است خیلی بزرگ باشد، شما باید باقی مانده‌ی آن به $1000000007 (10^9 + 7)$ را چاپ کنید. # ورودی در سطر اوّل ورودی عدد $q$، تعداد صحبت‌های که مسریکس با شما می‌کند، آمده است. هر یک از $q$ سطر بعد صحبت‌های مسریکس را به ترتیب زمان گفته شدنشان مشخّص می‌کنند. هر سطر ۲ حالت دارد! + `+ c t` یعنی «دیدم که $c$ پا متعلّق به دایناسور نژاد $t$ از روی پل رد شد.» + `?` یعنی «خیلی وقته کسی رد نشده. بگو تعداد پاهای این دایناسورها چند حالت داره؟» $$1 \leq q \leq 100\ 000$$ $$1 \leq c \leq 1\ 000\ 000$$ $$1 \leq t \leq 100\ 000$$ تضمین می‌شود مجموع تعداد پاهایی که از هر نژاد دایناسور مشاهده می‌شوند از $1\ 000\ 000$ بیشتر نخواهد شد. # خروجی تعداد سطرهای خروجی به تعداد صحبت‌های نوع دوم(`?`) است و در $i$-امین سطر باید پاسخ $i$-امین پرسش را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 + 30 1 + 10 2 ? + 2 2 ? ``` ## خروجی نمونه ۱ ``` 32 16 ```

فرهنگ

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

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

از آن جایی که اگر مسریکس حواسش نباشد ممکن است زیر پای کُرّه دایناسورها له شود، کنار یک بزرگ‌راه پنهان شده و به دایناسورهایی که از پل عابر پیاده‌ی بالای بزرگ‌راه رد می‌شوند نگاه می‌کند. البته چون یک بیلبورد تبلیغاتی جلوی پل عابر نصب شده است، مسریکس فقط می‌تواند از زیر بیلبورد، پاهای دایناسورها را ببیند. جالب است بدانید او می‌تواند از شکل پاهای دایناسورها، نژاد آن‌ها را بفهمد.

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

مثلا اگر مسریکس بگوید که «۱ پا متعلّق به نژاد ۱ روی پل عابر دیدم، بعد ۴ پا متعلّق به نژاد ۲ روی پل عابر دیدم و بعد ۱ پا متعلّق به نژاد ۱ دیدم و برای مدّت زمان طولانی دیگه پایی از روی پل عابر رد نشد، بگو تعداد حالات پاهای دایناسورها چند تاست.» شما باید به او بگویید ۶. چرا که ممکن است دایناسورهایی که از نژاد ۱ هستند ۱ یا ۲ پا داشته باشند و دایناسورهایی که از نژاد ۲ هستند می‌توانند ۱، ۲ یا ۴ پا داشته باشند. و اگر بعد از آن به شما بگوید که «۳ پا متعلّق به دایناسور نژاد ۲ دیدم و برای مدّت طولانی کسی از روی پل رد نشد، دوباره بگو چند حالت دارههه.» شما باید بگویید ۲! چرا که دایناسورهای نژاد ۲ فقط ۱ پا می‌توانند داشته باشند.

هم‌چنین مسریکس فرض می‌کند نژادهایی که تا به حال هیچ پایی از آن نوع از پل رد نشده است منقرض شده‌اند و شما نباید در شمارش تعداد حالات، به تعداد پاهای نژادهای مشاهده نشده اهمّیت بدهید. برای مثال اگر مسریکس پیش از آن که دایناسوری از پل عبور کند از شما تعداد حالات را بپرسد، شما باید در جواب عدد ۱ را بگویید.

حواستان باشد که هنگامی که مسریکس دو مرتبه پاهای یک نژاد را می‌بیند، اگر بین این دو مرتبه هیچ پرسشی نکرده باشد، ممکن است همه پاهایی که در این دو مرتبه دیده متعلّق به یک دایناسور باشد اما اگر بین آن‌ها پرسشی انجام داده باشد، قطعا پاهای دایناسورهای مختلف بوده‌اند.

مشاهدات مسریکس در ورودی آمده است. به ازای هر پرسش مسریکس، جواب آن پرسش را در خروجی چاپ کنید تا او بتواند جلوی گرمایش را بگیرد. فقط چون این مقدار ممکن است خیلی بزرگ باشد، شما باید باقی مانده‌ی آن به $1000000007 (10^9 + 7)$ را چاپ کنید.

ورودی🔗

در سطر اوّل ورودی عدد $q$ ، تعداد صحبت‌های که مسریکس با شما می‌کند، آمده است.

هر یک از $q$ سطر بعد صحبت‌های مسریکس را به ترتیب زمان گفته شدنشان مشخّص می‌کنند. هر سطر ۲ حالت دارد!

+ c t

یعنی «دیدم که $c$ پا متعلّق به دایناسور نژاد $t$ از روی پل رد شد.»

یعنی «خیلی وقته کسی رد نشده. بگو تعداد پاهای این دایناسورها چند حالت داره؟»

$1 \leq q \leq 100\ 000$ $1 \leq c \leq 1\ 000\ 000$ $1 \leq t \leq 100\ 000$

تضمین می‌شود مجموع تعداد پاهایی که از هر نژاد دایناسور مشاهده می‌شوند از $1\ 000\ 000$ بیشتر نخواهد شد.

خروجی🔗

تعداد سطرهای خروجی به تعداد صحبت‌های نوع دوم(?) است و در $i$ -امین سطر باید پاسخ $i$ -امین پرسش را چاپ کنید.

مثال🔗

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

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

32
16

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... «میسیکس» دوست و همراه قدیمی مِسِریکس بود که به علت بزرگ بودن و رد نشدن عقایدش از فیلتر‌‌های مِسِریکس دوستی‌شان ادامه پیدا نکرد. به اعتقاد میسیکس علت بحران محیط زیست خود ما آدم‌ها هستیم و باید نابود شویم. یک شب میسیکس به آزمایشگاه تحقیقات سلاح‌های شیمیایی حمله می‌کند تا تعدادی سم کشنده برای قتل عام بشریت بدزدد. او از قبل متوجه شده‌است که $k$ نوع سم کشنده در این آزمایشگاه وجود دارد و با $i$-امین سم می‌شود $p_i$ نفر را کشت. همچنین به ازای هر سم $i$ و $j$ می‌دانیم اگر به لوله‌ی آزمایش حاوی سم $j$، سم $i$ را اضافه کنیم سم $a_{i,j}$ بدست می‌آید. **توجه کنید که $a_{i,j}$ ممکن است با $a_{j,i}$ متفاوت باشد.** میسیکس در آزمایشگاه یک میز می‌بیند که روی آن $n$ لوله‌ی آزمایش حاوی سم قرار دارد. $i$-امین لوله دارای سم $t_i$ است. وقت او اندک است و می‌خواهد تعدادی از سم‌ها را بدزدد که با آن‌ها بتواند در مجموع بیشترین تعداد آدم را بکشد. چون او از قبل جدول تبدیل مواد را دارد می‌تواند در مراحلی هر بار یکی از دو کار زیر را انجام دهد: + دو لوله آزمایش که **کنار هم** هستند (یعنی در میان آن‌ها لوله‌ای نیست) را بردارد و **چپی را درون راستی** بریزد و لوله چپی را دور بیندازد. یعنی اگر در لوله چپ سم $x$ باشد و در لوله راست سم $y$ باشد با ریختن چپی در راستی به سم $a_{x,y}$ می‌رسیم. + یکی از لوله‌ها را بردارد و در ساکش بگذارد. مِسِریکس متوجه حمله میسیکس به آزمایشگاه شده‌است و می‌خواهد محاسبه کند سم‌هایی که او دزدیده‌است حداکثر چند نفر را می‌کشند چون این تعداد قطعا پارامتری موثّر در بحران محیط زیست است. # ورودی در سطر اول ورودی به ترتیب دو عدد $k$ و $n$ آمده‌است. در سطر دوم $k$ عدد آمده‌است که عدد $i$-ام برابر با $p_i$ است. در $i$-امین سطر از $k$ سطر بعدی $k$ عدد آمده‌است که عدد $j$-ام برابر با $a_{i,j}$ است. سپس در سطر آخر $n$ عدد آمده‌است که عدد $i$-ام برابر با $t_i$ است. $$1 \le k \le 30$$ $$1 \le n \le 85$$ $$0 \le p_i \le 1\ 000\ 000$$ $$1 \le a_{i,j} \le k$$ $$1 \le t_i \le k$$ # خروجی در تنها سطر خروجی حداکثر تعداد نفراتی که میسیکس با دستکاری و دزدیدن سم‌ها می‌تواند بکشد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 9 2 3 6 5 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 2 2 2 2 ``` ## خروجی نمونه ۱ ``` 29 ``` با توجه به جدول تبدیل و هزینه‌ها تنها به‌صرفه است که ۱ و ۲ را ترکیب کنیم و به ۳ برسیم. برای رسیدن به جواب بهینه ابتدا سم ۴ را می‌دزدیم و سپس چهار بار لوله سم ۱ را درون لوله سم ۲ می‌ریزد و به سم ۳ می‌رسد و آن را درون کیفش می‌گذارد. در نهایت او یک سم ۴ دارد و چهار سم ۳ و جمع تعداد نفراتی که این سموم می‌کشند ۲۹ می‌شود.

قتل عام

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

«میسیکس» دوست و همراه قدیمی مِسِریکس بود که به علت بزرگ بودن و رد نشدن عقایدش از فیلتر‌‌های مِسِریکس دوستی‌شان ادامه پیدا نکرد. به اعتقاد میسیکس علت بحران محیط زیست خود ما آدم‌ها هستیم و باید نابود شویم.

یک شب میسیکس به آزمایشگاه تحقیقات سلاح‌های شیمیایی حمله می‌کند تا تعدادی سم کشنده برای قتل عام بشریت بدزدد. او از قبل متوجه شده‌است که $k$ نوع سم کشنده در این آزمایشگاه وجود دارد و با $i$ -امین سم می‌شود $p_i$ نفر را کشت. همچنین به ازای هر سم $i$ و $j$ می‌دانیم اگر به لوله‌ی آزمایش حاوی سم $j$ ، سم $i$ را اضافه کنیم سم $a_{i,j}$ بدست می‌آید. توجه کنید که $a_{i,j}$ ممکن است با $a_{j,i}$ متفاوت باشد.

میسیکس در آزمایشگاه یک میز می‌بیند که روی آن $n$ لوله‌ی آزمایش حاوی سم قرار دارد. $i$ -امین لوله دارای سم $t_i$ است. وقت او اندک است و می‌خواهد تعدادی از سم‌ها را بدزدد که با آن‌ها بتواند در مجموع بیشترین تعداد آدم را بکشد. چون او از قبل جدول تبدیل مواد را دارد می‌تواند در مراحلی هر بار یکی از دو کار زیر را انجام دهد:

دو لوله آزمایش که کنار هم هستند (یعنی در میان آن‌ها لوله‌ای نیست) را بردارد و چپی را درون راستی بریزد و لوله چپی را دور بیندازد. یعنی اگر در لوله چپ سم $x$ باشد و در لوله راست سم $y$ باشد با ریختن چپی در راستی به سم $a_{x,y}$ می‌رسیم.
یکی از لوله‌ها را بردارد و در ساکش بگذارد.

مِسِریکس متوجه حمله میسیکس به آزمایشگاه شده‌است و می‌خواهد محاسبه کند سم‌هایی که او دزدیده‌است حداکثر چند نفر را می‌کشند چون این تعداد قطعا پارامتری موثّر در بحران محیط زیست است.

ورودی🔗

در سطر اول ورودی به ترتیب دو عدد $k$ و $n$ آمده‌است.

در سطر دوم $k$ عدد آمده‌است که عدد $i$ -ام برابر با $p_i$ است.

در $i$ -امین سطر از $k$ سطر بعدی $k$ عدد آمده‌است که عدد $j$ -ام برابر با $a_{i,j}$ است.

سپس در سطر آخر $n$ عدد آمده‌است که عدد $i$ -ام برابر با $t_i$ است.

$1 \le k \le 30$ $1 \le n \le 85$ $0 \le p_i \le 1\ 000\ 000$ $1 \le a_{i,j} \le k$ $1 \le t_i \le k$

خروجی🔗

در تنها سطر خروجی حداکثر تعداد نفراتی که میسیکس با دستکاری و دزدیدن سم‌ها می‌تواند بکشد را چاپ کنید.

مثال🔗

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

4 9
2 3 6 5
1 3 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 4 2 2 2 2

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

با توجه به جدول تبدیل و هزینه‌ها تنها به‌صرفه است که ۱ و ۲ را ترکیب کنیم و به ۳ برسیم. برای رسیدن به جواب بهینه ابتدا سم ۴ را می‌دزدیم و سپس چهار بار لوله سم ۱ را درون لوله سم ۲ می‌ریزد و به سم ۳ می‌رسد و آن را درون کیفش می‌گذارد. در نهایت او یک سم ۴ دارد و چهار سم ۳ و جمع تعداد نفراتی که این سموم می‌کشند ۲۹ می‌شود.

+ محدودیت زمان: ۱٫۵ ثانیه + محدودیت حافظه: **۵۱۲ مگابایت** ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... مسریکس می‌خواهد گریزی بزند به روابط فامیلی بلکه بتواند راه حل رفع بحران محیط زیست را از این طریق بیابد. از نظر مسریکس، گام نخست تحقیق در این زمینه، تسلّط بر تعاریف زیر است. + پدر: این تعریف خیلی جدیدی نیست. هر کسی(به جز بزرگ‌خاندان) فرزند دقیقا یک انسان دیگر است که آن را پدرش می‌نامیم. + بزرگ‌خاندان: کسی که فرض می‌کنیم پدری ندارد. + پدرِ $i$-ام: اگر $i > 0$ باشد، پدرِ پدرِ $i-1$-ام یک انسان را پدر $i$-ام او می‌نامیم. پدر ۰-ام هر کسی، خود او است. + عمو: می‌گوییم انسان $X$ عموی انسان $Y$ است اگر و فقط اگر پدر $a$-ام $X$ و پدر $b$-ام $Y$ برابر باشند. + دایی: می‌گوییم انسان $X$ دایی انسان $Y$ است اگر و فقط اگر پدر $c$-ام $X$ و پدر $d$-ام $Y$ برابر باشند. دقّت کنید که در تعریف عمو، پدر $a$-ام $X$ یا پدر $b$-ام $Y$ وجود نداشته باشند، $X$ عموی $Y$ نخواهد بود. هم‌چنین اگر در تعریف دایی، پدر $c$-ام $X$ و یا پدر $d$-ام $Y$ وجود نداشته باشد نیز $X$ دایی $Y$ نخواهد بود. روزی مسریکس داشت با میسیکس، که علاوه بر دوست قدیمی مسریکس، یکی از اقوام دور او هم هست، در خیابان قدم می‌زد و در مورد بحران محیط زیست صحبت می‌کرد که ناگهان دو نفر جلوی آن‌ها را گرفتند و از مسریکس پرسیدند: «میسیکس چه نسبتی با تو داره؟» و «تو چه نسبتی با میسیکس داری؟». مسریکس برای پاسخ دادن به این سوال چند لحظه در فکر فرو رفت. و به نکته‌ی جالبی پِی برد؛ هر دو آن‌ها می توانستند با دنباله‌ای از کلمات عمو و دایی نسبتشان با یکدیگر را توضیح دهند؛ مثلن در جواب سوال اوّل مسریکس می‌توانست بگوید: «میسیکس **عمویِ عمویِ داییِ داییِ** من است.» و در جواب سوال دوم بگوید: «من **داییِ عمویِ عمویِ داییِ** میسیکس هستم.» ناگهان مسریکس به نکته‌ی جالب‌تری پی برد؛ بله او پارامتر جدیدی پیدا کرد که واقعا در بحران محیط زیست مؤثر است؛ این پارامتر را در خانواده‌ی مسریکس محاسبه کنید و به او بگویید. فرض کنید که خانواده از $n$ نفر تشکیل شده باشد و هر انسان را با عددی یکتا از $1$ تا $n$ نمایش دهیم. بزرگ‌خاندان همواره با عدد ۱ مشخّص می‌شود. و پدر هر کسی به جز بزرگ‌خاندان شخصی یکتاست. شما باید تعداد جفت انسان‌هایی را بشمرید که ‌می‌توانند همدیگر را با دنباله‌ای از کلمات **عمو** و **دایی** صدا بزنند. # ورودی در سطر اوّل ورودی عدد $n$ می‌آید. در سطر دوم دو عدد $a$ و $b$ می‌آیند. در سطر سوم نیز دو عدد $c$ و $d$ می‌آیند. هر یک از $n - 1$ خط بعد نشان‌دهنده‌ی پدر انسان‌ها هستند. در خط $i$-ام شماره‌ی پدر انسان $i + 1$-ام می‌آید. تضمین می‌شود که شماره‌ی پدر هر کسی از شماره‌ی خود او کوچک‌تر است. $$1 \leq a, b, c, d \leq n \leq 500\ 000$$ # خروجی در تنها سطر خروجی باید تعداد جفت‌هایی که می‌توانند هم‌دیگر را با دنباله‌ای از کلمات **عمو** و **دایی** صدا کنند، چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 1 3 2 1 1 2 2 4 ``` ## خروجی نمونه ۱ ``` 6 ``` در این مثال همه جفت‌ها به جز جفت‌هایی که شامل راس ۱ هستند، می توانند یکدیگر را با دنباله‌ای از کلمات عمو و دایی صدا بزنند.

باجی

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

مسریکس می‌خواهد گریزی بزند به روابط فامیلی بلکه بتواند راه حل رفع بحران محیط زیست را از این طریق بیابد.

از نظر مسریکس، گام نخست تحقیق در این زمینه، تسلّط بر تعاریف زیر است.

پدر: این تعریف خیلی جدیدی نیست. هر کسی(به جز بزرگ‌خاندان) فرزند دقیقا یک انسان دیگر است که آن را پدرش می‌نامیم.
بزرگ‌خاندان: کسی که فرض می‌کنیم پدری ندارد.
پدرِ $i$ -ام: اگر $i > 0$ باشد، پدرِ پدرِ $i-1$ -ام یک انسان را پدر $i$ -ام او می‌نامیم. پدر ۰-ام هر کسی، خود او است.
عمو: می‌گوییم انسان $X$ عموی انسان $Y$ است اگر و فقط اگر پدر $a$ -ام $X$ و پدر $b$ -ام $Y$ برابر باشند.
دایی: می‌گوییم انسان $X$ دایی انسان $Y$ است اگر و فقط اگر پدر $c$ -ام $X$ و پدر $d$ -ام $Y$ برابر باشند.

دقّت کنید که در تعریف عمو، پدر $a$ -ام $X$ یا پدر $b$ -ام $Y$ وجود نداشته باشند، $X$ عموی $Y$ نخواهد بود. هم‌چنین اگر در تعریف دایی، پدر $c$ -ام $X$ و یا پدر $d$ -ام $Y$ وجود نداشته باشد نیز $X$ دایی $Y$ نخواهد بود.

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

مسریکس برای پاسخ دادن به این سوال چند لحظه در فکر فرو رفت. و به نکته‌ی جالبی پِی برد؛ هر دو آن‌ها می توانستند با دنباله‌ای از کلمات عمو و دایی نسبتشان با یکدیگر را توضیح دهند؛ مثلن در جواب سوال اوّل مسریکس می‌توانست بگوید: «میسیکس عمویِ عمویِ داییِ داییِ من است.» و در جواب سوال دوم بگوید: «من داییِ عمویِ عمویِ داییِ میسیکس هستم.»

ناگهان مسریکس به نکته‌ی جالب‌تری پی برد؛ بله او پارامتر جدیدی پیدا کرد که واقعا در بحران محیط زیست مؤثر است؛ این پارامتر را در خانواده‌ی مسریکس محاسبه کنید و به او بگویید.

فرض کنید که خانواده از $n$ نفر تشکیل شده باشد و هر انسان را با عددی یکتا از $1$ تا $n$ نمایش دهیم. بزرگ‌خاندان همواره با عدد ۱ مشخّص می‌شود. و پدر هر کسی به جز بزرگ‌خاندان شخصی یکتاست. شما باید تعداد جفت انسان‌هایی را بشمرید که ‌می‌توانند همدیگر را با دنباله‌ای از کلمات عمو و دایی صدا بزنند.

ورودی🔗

در سطر اوّل ورودی عدد $n$ می‌آید.

در سطر دوم دو عدد $a$ و $b$ می‌آیند.

در سطر سوم نیز دو عدد $c$ و $d$ می‌آیند.

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

$1 \leq a, b, c, d \leq n \leq 500\ 000$

خروجی🔗

در تنها سطر خروجی باید تعداد جفت‌هایی که می‌توانند هم‌دیگر را با دنباله‌ای از کلمات عمو و دایی صدا کنند، چاپ کنید.

مثال🔗

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

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

در این مثال همه جفت‌ها به جز جفت‌هایی که شامل راس ۱ هستند، می توانند یکدیگر را با دنباله‌ای از کلمات عمو و دایی صدا بزنند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... حتما داستان هنرنمایی لیته و فیته بر روی صحنه را به یاد دارید. اکنون، مدّت زیادی از آن هنرنمایی می‌گذرد و لیته و فیته حسابی هنرمندان ماهری شده‌اند. مسریکس همراه با باقر و بی‌قر، دو نفر از دوستانش، برای تماشای هنرنمایی جدید لیته و فیته به سالن تئاتر رفته است. در همان لحظه فکری هوشمندانه به ذهن مسریکس می‌رسد و به باقر و بی‌قر می‌گوید هر کدام دو صندلی خالی از دو ردیف مختلف سالن تئاتر انتخاب کنند. به عبارت دیگر، باقر باید یک ردیف را انتخاب کند و سپس از آن ردیف دو صندلی خالی انتخاب کند. سپس بی‌قر باید یک ردیف دیگر را انتخاب کرده و دو صندلی خالی از آن ردیف انتخاب کند. در سالن تئاتر $n$ صندلی خالی وجود دارد. فرض کنید باقر صندلی‌های شماره‌ی $t_1$ و $t_2$ را از سطر $r_1$ انتخاب کند و بی‌قر صندلی‌های شماره‌ی $s_1$ و $s_2$ را از سطر $r_2$ انتخاب کند. این ۴ صندلی را باقرپسند می‌گوییم اگر ۲ شرط زیر به ازای آن‌ها برقرار باشد. + $r_1 < r_2$ + $t_1 < s_1 < t_2 < s_2$ و آن‌ها را بی‌قرپسند می‌گوییم اگر ۲ شرط زیر به ازای آن‌ها برقرار باشد. + $r_1 < r_2$ + $s_1 < t_1 < s_2 < t_2$ مسریکس می‌خواهد «تعداد حالاتی که ۴ صندلی انتخاب شده بی‌قرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» را محاسبه کند تا بر اساس آن‌ها راهکاری برای بحران محیط زیست پیدا کند. لطفا باقی‌مانده‌ی این مقدار به $1\ 000\ 000\ 007$ را برای مسریکس محاسبه کنید. برای راحتی فرض کنید سالن تئاتر متشکّل از $n$ ستون است و در هر ستون دقیقا یک صندلی خالی وجود دارد. شماره‌ی ردیف صندلی خالی‌ای که در ستون $i$ام قرار دارد برابر با $a_i$ است. # ورودی در سطر اوّل ورودی عدد $n$ آمده است. در سطر دوم $n$ عدد آمده است که نشان‌دهنده‌ی آرایه‌ی $a$ هستند. $$1 \le n \le 100\ 000$$ $$1 \leq a_i\leq 10^9$$ # خروجی در تنها سطر خروجی، باقی مانده‌ی «تعداد حالاتی که ۴ صندلی انتخاب شده بی‌قرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» به $1\ 000\ 000\ 007$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 6 2 2 1 2 1 2 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 9 2 2 1 2 1 3 2 2 2 ``` ## خروجی نمونه ۲ ``` 1000000006 ``` **توضیح:** در این مثال، اختلاف تعداد حالاتِ گفته شده برابر $-1$ است که باقی‌مانده‌اش به $1\ 000\ 000\ 007$ برابر با مقدار چاپ شده است.

فرق

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

حتما داستان هنرنمایی لیته و فیته بر روی صحنه را به یاد دارید. اکنون، مدّت زیادی از آن هنرنمایی می‌گذرد و لیته و فیته حسابی هنرمندان ماهری شده‌اند.

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

در سالن تئاتر $n$ صندلی خالی وجود دارد. فرض کنید باقر صندلی‌های شماره‌ی $t_1$ و $t_2$ را از سطر $r_1$ انتخاب کند و بی‌قر صندلی‌های شماره‌ی $s_1$ و $s_2$ را از سطر $r_2$ انتخاب کند.

این ۴ صندلی را باقرپسند می‌گوییم اگر ۲ شرط زیر به ازای آن‌ها برقرار باشد.

$r_1 < r_2$
$t_1 < s_1 < t_2 < s_2$

و آن‌ها را بی‌قرپسند می‌گوییم اگر ۲ شرط زیر به ازای آن‌ها برقرار باشد.

$r_1 < r_2$
$s_1 < t_1 < s_2 < t_2$

مسریکس می‌خواهد «تعداد حالاتی که ۴ صندلی انتخاب شده بی‌قرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» را محاسبه کند تا بر اساس آن‌ها راهکاری برای بحران محیط زیست پیدا کند. لطفا باقی‌مانده‌ی این مقدار به $1\ 000\ 000\ 007$ را برای مسریکس محاسبه کنید.

برای راحتی فرض کنید سالن تئاتر متشکّل از $n$ ستون است و در هر ستون دقیقا یک صندلی خالی وجود دارد. شماره‌ی ردیف صندلی خالی‌ای که در ستون $i$ ام قرار دارد برابر با $a_i$ است.

ورودی🔗

در سطر اوّل ورودی عدد $n$ آمده است.

در سطر دوم $n$ عدد آمده است که نشان‌دهنده‌ی آرایه‌ی $a$ هستند.

$1 \le n \le 100\ 000$ $1 \leq a_i\leq 10^9$

خروجی🔗

در تنها سطر خروجی، باقی مانده‌ی «تعداد حالاتی که ۴ صندلی انتخاب شده بی‌قرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» به $1\ 000\ 000\ 007$ را چاپ کنید.

مثال🔗

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

6
2 2 1 2 1 2

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

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

9
2 2 1 2 1 3 2 2 2

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

1000000006

توضیح: در این مثال، اختلاف تعداد حالاتِ گفته شده برابر $-1$ است که باقی‌مانده‌اش به $1\ 000\ 000\ 007$ برابر با مقدار چاپ شده است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... همان طور که می‌دانید یکی از دلایل گرم شدن زمین ترافیک سنگین در جادّه‌های شهر است. آقای شهردار تصمیم گرفته است که طول جادّه‌های شهر را طوری تغییر دهد که زمین کمی سردتر شود. او که آوازه‌ی مسریکس به گوشش رسیده، برای این کار از مسریکس کمک می‌گیرد. شهر به شکل یک گراف وزن‌دار $n$ راسی و $m$ یالی است که رئوس آن تقاطع‌های شهر هستند و یال‌های آن جادّه‌های دوطرفه‌ی شهر هستند. وزن یال‌ها نیز طول جادّه‌هاست. به نظر مسریکس باید طول تمام جادّه‌ها به میزان $w$ که عددی نامنفی است افزایش پیدا کند. هم‌چنین اگر فاصله‌ی کوتاه‌ترین مسیر از تقاطع $p_1$ به تقاطع $i$ را $dis_i$ بنامیم، برای کمینه کردن گرمای زمین باید $w$ طوری انتخاب شود که به ازای هر $i$ ($1 \leq i \leq n - 1$): $$dis_{p_i} \leq dis_{p_{i + 1}}$$ در این عبارت $p$ جایگشتی‌است که مسریکس با توجّه به گراف شهر در نظر گرفته است و در ورودی داده می‌شود. ما گراف ابتدایی شهر را به شما می‌دهیم، شما **کم‌ترین مقدار نامنفی $w$** را پیدا کنید که اگر به طول هر جادّه $w$ واحد اضافه کنیم، شرط بالا برقرار شود. اگر هیچ مقدار مطلوب $w$ وجود نداشت هم بگویید چنین $w$ وجود ندارد. # ورودی در سطر اوّل ورودی اعداد $n$ و $m$ می‌آیند. در هر یک از $m$ سطر بعد سه عدد $u$، $v$ و $w$ می‌آید. چنین خطی به این معنی است که بین تقاطع $u$ و $v$ جادّه‌ای به طول $w$ وجود دارد. در خط بعد $n$ عدد می‌آید. این $n$ عدد نشان‌دهنده‌ی **جایگشت** $p$ هستند. تضمین می‌شود گراف ورودی همبند است. $$1 \leq n \leq 500$$ $$n - 1 \leq m \leq 10\ 000$$ $$1 \leq u, v \leq n$$ $$u \neq v$$ $$1 \leq w \leq 1\ 000\ 000$$ # خروجی اگر هیچ مقدار مطلوب $w$ وجود ندارد، در تنها سطر خروجی عبارت `No` چاپ کنید. در غیر این صورت در خط اوّل عبارت `Yes` چاپ کنید و در خط دوم کوچک‌ترین مقدار ممکن و نامنفی $w$ را چاپ کنید. جواب شما درست در نظر گرفته می‌شود اگر و تنها اگر اختلاف مطلق و نسبی اش با پاسخ صحیح حداکثر $10^{-6}$ باشد. # مثال ## ورودی نمونه ۱ ``` 6 6 1 2 1 2 3 1 1 4 5 4 5 5 5 6 5 1 6 20 1 2 4 3 6 5 ``` ## خروجی نمونه ۱ ``` Yes 10.00000000 ``` ## ورودی نمونه ۲ ``` 6 6 1 2 1 2 3 1 1 4 5 4 5 5 5 6 5 1 6 20 1 2 4 6 3 5 ``` ## خروجی نمونه ۲ ``` Yes 18.00000000 ``` ## ورودی نمونه ۲ ``` 6 6 1 2 1 2 3 1 1 4 5 4 5 5 5 6 5 1 6 20 1 2 4 6 5 3 ``` ## خروجی نمونه ۲ ``` No ```

ترتیب

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

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

شهر به شکل یک گراف وزن‌دار $n$ راسی و $m$ یالی است که رئوس آن تقاطع‌های شهر هستند و یال‌های آن جادّه‌های دوطرفه‌ی شهر هستند. وزن یال‌ها نیز طول جادّه‌هاست. به نظر مسریکس باید طول تمام جادّه‌ها به میزان $w$ که عددی نامنفی است افزایش پیدا کند. هم‌چنین اگر فاصله‌ی کوتاه‌ترین مسیر از تقاطع $p_1$ به تقاطع $i$ را $dis_i$ بنامیم، برای کمینه کردن گرمای زمین باید $w$ طوری انتخاب شود که به ازای هر $i$ ( $1 \leq i \leq n - 1$ ):

$dis_{p_i} \leq dis_{p_{i + 1}}$

در این عبارت $p$ جایگشتی‌است که مسریکس با توجّه به گراف شهر در نظر گرفته است و در ورودی داده می‌شود.

ما گراف ابتدایی شهر را به شما می‌دهیم، شما کم‌ترین مقدار نامنفی $w$ را پیدا کنید که اگر به طول هر جادّه $w$ واحد اضافه کنیم، شرط بالا برقرار شود. اگر هیچ مقدار مطلوب $w$ وجود نداشت هم بگویید چنین $w$ وجود ندارد.

ورودی🔗

در سطر اوّل ورودی اعداد $n$ و $m$ می‌آیند.

در هر یک از $m$ سطر بعد سه عدد $u$ ، $v$ و $w$ می‌آید. چنین خطی به این معنی است که بین تقاطع $u$ و $v$ جادّه‌ای به طول $w$ وجود دارد.

در خط بعد $n$ عدد می‌آید. این $n$ عدد نشان‌دهنده‌ی جایگشت $p$ هستند.

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

$1 \leq n \leq 500$ $n - 1 \leq m \leq 10\ 000$ $1 \leq u, v \leq n$ $u \neq v$ $1 \leq w \leq 1\ 000\ 000$

خروجی🔗

اگر هیچ مقدار مطلوب $w$ وجود ندارد، در تنها سطر خروجی عبارت No چاپ کنید. در غیر این صورت در خط اوّل عبارت Yes چاپ کنید و در خط دوم کوچک‌ترین مقدار ممکن و نامنفی $w$ را چاپ کنید. جواب شما درست در نظر گرفته می‌شود اگر و تنها اگر اختلاف مطلق و نسبی اش با پاسخ صحیح حداکثر $10^{-6}$ باشد.

مثال🔗

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

6 6
1 2 1
2 3 1
1 4 5
4 5 5
5 6 5
1 6 20
1 2 4 3 6 5

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

Yes
10.00000000

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

6 6
1 2 1
2 3 1
1 4 5
4 5 5
5 6 5
1 6 20
1 2 4 6 3 5

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

Yes
18.00000000

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

6 6
1 2 1
2 3 1
1 4 5
4 5 5
5 6 5
1 6 20
1 2 4 6 5 3

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

No

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... تعدادی از دوستان مسریکس به تازگی در اینستاگرام ثبت نام کرده‌اند و برخی از آن‌ها یکدیگر را دنبال کرده‌اند. از آن‌جایی که دوستان مسریکس طرز فکر مشابهی دارند، هر گاه کسی عکسی در صفحه‌اش قرار می‌دهد تمام دنبال‌کننده‌هایش نیز همان عکس را در صفحه‌ی خودشان قرار می‌دهند. البته آن‌ها حواسشان هست که یک عکس را بیش از یک بار در صفحه‌شان پست نکنند. روزی مسریکس عکسی در صفحه‌اش قرار داد. بعد از چند روز متوجّه شد بعضی از افرادی که دنبال می‌کند عکس او را در صفحه‌شان پست کرده‌اند. حس رضایتی در درونش ایجاد شد و با خودش گفت: «واهاهاییی... من چه قدر خفنم. عکس‌هام تو صفحه‌ی بقیّه‌ی مردم هم پخش شده.» امّا بلافاصله یادش افتاد غرور چیز خوبی نیست و زبانش را گاز گرفت. مدّتی بعد با خودش فکر کرد که چه قدر این موضوع به بحران محیط زیست مربوط است. پس تصمیم گرفت که از شما بپرسد کدام یک از افراد هستند که اگر حساب کاربری‌شان را پاک کنیم می‌توانیم مطمئن باشیم تحت هیچ شرایطی کسی با خودش فکر نمی‌کند که «واهاهاییی... من چه قدر خفنم. عکس‌هام تو صفحه‌ی بقیّه‌ی مردم هم پخش شده.» دقّت کنید که دنبال کردن رابطه‌ی دو طرفه نیست و هر کسی فقط عکس‌های کسانی را می‌بیند که دنبالشان کرده است. هم‌چنین با حذف کردن هر کدام از افراد داخل لیست به تنهایی باید شرط مساله برقرار شود، نه حذف هم‌زمان تمام افراد لیست. **هم‌چنین تضمین می‌شود که در ابتدا اگر شخص دلخواه $a$ عکسی در صفحه‌اش بگذارد شخص دلخواه $b$ قطعا آن عکس را پس از تعدادی روز در صفحه‌ی کسانی که دنبال می‌کند خواهد دید.** # ورودی در سطر اوّل ورودی عدد $n$ و $m$ که به ترتیب بیان‌گر تعداد افراد حاضر در اینستاگرام و تعداد روابط دنبال‌کردن می‌آیند. در هر یک از $m$ خط بعد دو عدد $a$ و $b$ می‌آید. به این معنی که فرد $a$ در اینستاگرام فرد $b$ را دنبال می‌کند. تضمین می‌شود که هیچ کدام از این $m$ سطر تکراری نیستند. $$1 \leq n \leq 100\ 000$$$$1 \leq m \leq 200\ 000$$ $$1 \leq a, b \leq n$$ $$a \neq b$$ # خروجی در سطر اوّل خروجی تعداد افرادی را چاپ کنید که اگر حساب کاربری هر کدام از آن‌ها پاک شود کسی عکس‌های خودش را در صفحه‌ی کسانی که آن‌ها را دنبال می‌کند نخواهد دید. در سطر دوم شماره‌ی این افراد را به ترتیب از کم به زیاد چاپ کنید. این اعداد باید با یک `space` از هم جدا شوند. # مثال ## ورودی نمونه ۱ ``` 6 7 1 2 2 3 3 5 2 4 5 6 4 6 6 1 ``` ## خروجی نمونه ۱ ``` 3 1 2 6 ``` **توضیح:** مثلا اگر در این سناریو کاربر شماره‌ی ۳ را حذف کنیم، ممکن است کاربر ۱ عکسی در صفحه‌اش قرار دهد، سپس کاربر ۶ آن را قرار می‌دهد، سپس کاربر ۴ و سپس کاربر ۲. بعد از این زنجیره از اتّفاقات، کاربر ۱ عکس خودش را در صفحه‌ی کاربر ۲ خواهد دید. در مورد حذف کاربر ۴ و یا ۵ نیز شرایط مشابهی برقرار است.

غرور

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

تعدادی از دوستان مسریکس به تازگی در اینستاگرام ثبت نام کرده‌اند و برخی از آن‌ها یکدیگر را دنبال کرده‌اند. از آن‌جایی که دوستان مسریکس طرز فکر مشابهی دارند، هر گاه کسی عکسی در صفحه‌اش قرار می‌دهد تمام دنبال‌کننده‌هایش نیز همان عکس را در صفحه‌ی خودشان قرار می‌دهند. البته آن‌ها حواسشان هست که یک عکس را بیش از یک بار در صفحه‌شان پست نکنند.

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

مدّتی بعد با خودش فکر کرد که چه قدر این موضوع به بحران محیط زیست مربوط است. پس تصمیم گرفت که از شما بپرسد کدام یک از افراد هستند که اگر حساب کاربری‌شان را پاک کنیم می‌توانیم مطمئن باشیم تحت هیچ شرایطی کسی با خودش فکر نمی‌کند که «واهاهاییی... من چه قدر خفنم. عکس‌هام تو صفحه‌ی بقیّه‌ی مردم هم پخش شده.»

دقّت کنید که دنبال کردن رابطه‌ی دو طرفه نیست و هر کسی فقط عکس‌های کسانی را می‌بیند که دنبالشان کرده است. هم‌چنین با حذف کردن هر کدام از افراد داخل لیست به تنهایی باید شرط مساله برقرار شود، نه حذف هم‌زمان تمام افراد لیست.

هم‌چنین تضمین می‌شود که در ابتدا اگر شخص دلخواه $a$ عکسی در صفحه‌اش بگذارد شخص دلخواه $b$ قطعا آن عکس را پس از تعدادی روز در صفحه‌ی کسانی که دنبال می‌کند خواهد دید.

ورودی🔗

در سطر اوّل ورودی عدد $n$ و $m$ که به ترتیب بیان‌گر تعداد افراد حاضر در اینستاگرام و تعداد روابط دنبال‌کردن می‌آیند.

در هر یک از $m$ خط بعد دو عدد $a$ و $b$ می‌آید. به این معنی که فرد $a$ در اینستاگرام فرد $b$ را دنبال می‌کند. تضمین می‌شود که هیچ کدام از این $m$ سطر تکراری نیستند.

$1 \leq n \leq 100\ 000$ $1 \leq m \leq 200\ 000$ $1 \leq a, b \leq n$ $a \neq b$

خروجی🔗

در سطر اوّل خروجی تعداد افرادی را چاپ کنید که اگر حساب کاربری هر کدام از آن‌ها پاک شود کسی عکس‌های خودش را در صفحه‌ی کسانی که آن‌ها را دنبال می‌کند نخواهد دید.

در سطر دوم شماره‌ی این افراد را به ترتیب از کم به زیاد چاپ کنید. این اعداد باید با یک space از هم جدا شوند.

مثال🔗

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

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

3
1 2 6

توضیح: مثلا اگر در این سناریو کاربر شماره‌ی ۳ را حذف کنیم، ممکن است کاربر ۱ عکسی در صفحه‌اش قرار دهد، سپس کاربر ۶ آن را قرار می‌دهد، سپس کاربر ۴ و سپس کاربر ۲. بعد از این زنجیره از اتّفاقات، کاربر ۱ عکس خودش را در صفحه‌ی کاربر ۲ خواهد دید. در مورد حذف کاربر ۴ و یا ۵ نیز شرایط مشابهی برقرار است.