====== 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$‎ عدد بنویسید که شماره‌ی بازه‌های انتخابی را مشخص می‌کند. شما باید شماره‌ی بازه‌ها را به ترتیب صعودی بنویسید. در ضمن این شماره‌ها با فاصله از هم جدا کنید. ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 2‎ \\ -‎1 1‎ \\ 2 3‎ \\ -‎1 3 | 1 \\ 1 2 | |2 2‎ \\ 0 2‎ \\ 2 3 | 2 \\ 1 2 | * [[سوال ۳۶|سوال بعد]] * [[سوال ۳۴|سوال قبل]]