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$ عدد بنویسید که شماره‌ی بازه‌های انتخابی را مشخص می‌کند. شما باید شماره‌ی بازه‌ها را به ترتیب صعودی بنویسید. در ضمن این شماره‌ها با فاصله از هم جدا کنید.

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