Segment

روی محور اعداد ‎$n$‎ بازه ی بسته به شما داده شده است. یک رنگ‌آمیزی از بازه‌ها معتبر است اگر هیچ دو بازه‌ی هم‌رنگی اشتراک نداشته باشند‎ (دو بازه اشتراک دارند اگر در حداقل یک نقطه مشترک باشند). یک عدد ‎$x$‎ به شما داده می شود. شما بایستی ‎$x$‎ تا از این ‎$n$‎ بازه را انتخاب کنید طوری که بتوان با کم‌ترین تعداد رنگ، یک رنگ‌آمیزی معتبر برای آن‌ها ارائه کرد.‎

برنامه‌ای بنویسید که

• اعداد ‎$n$‎ و ‎$x$‎ و مشخصات بازه‌ها را از ورودی بخواند.
• کم‌ترین تعداد رنگ برای رنگ کردن بازه‌ها و نحوه‌ی رنگ کردن آن‌ها با این تعداد رنگ را بیابد و در خروجی بنویسید.

• در سطر نخست ورودی دو عدد صحیح ‎$n$‎ و ‎$x$‎ به ترتیب نوشته شده‌اند.
• در ‎$n$‎ سطر بعد، مشخصات ‎$n$‎ بازه آمده است. در سط ‎$i+1$‎ام دو عدد نوشته شده است که به ترتیب ابتدا و انتهای بازه‌ی ‎$i$‎ام را مشخص می کنند.‎
• ‎$1 \leq n \leq 100000$ (در ‎$40$‎ درصد تست‌ها ‎$n \leq 300$‎ می باشد).
• ‎$1 \leq x \leq n$.

• در سطر نخست خروجی، کم‌ترین تعداد رنگ لازم برای رنگ‌آمیزی معتبر ‎$x$‎ بازه‌ی انتخابی را بنویسید.‎
• در سطر دوم ‎$x$‎ عدد بنویسید که شماره‌ی بازه‌های انتخابی را مشخص می‌کند. شما باید شماره‌ی بازه‌ها را به ترتیب صعودی بنویسید. در ضمن این شماره‌ها با فاصله از هم جدا کنید.

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

• سوال بعد
• سوال قبل