Segment
روی محور اعداد n بازه ی بسته به شما داده شده است. یک رنگآمیزی از بازهها معتبر است اگر هیچ دو بازهی همرنگی اشتراک نداشته باشند (دو بازه اشتراک دارند اگر در حداقل یک نقطه مشترک باشند). یک عدد x به شما داده می شود. شما بایستی x تا از این n بازه را انتخاب کنید طوری که بتوان با کمترین تعداد رنگ، یک رنگآمیزی معتبر برای آنها ارائه کرد.
برنامهای بنویسید که
ورودی
در سطر نخست ورودی دو عدد صحیح n و x به ترتیب نوشته شدهاند.
در n سطر بعد، مشخصات n بازه آمده است. در سط i+1ام دو عدد نوشته شده است که به ترتیب ابتدا و انتهای بازهی iام را مشخص می کنند.
1≤n≤100000 (در 40 درصد تستها n≤300 می باشد).
1≤x≤n.
خروجی
در سطر نخست خروجی، کمترین تعداد رنگ لازم برای رنگآمیزی معتبر x بازهی انتخابی را بنویسید.
در سطر دوم x عدد بنویسید که شمارهی بازههای انتخابی را مشخص میکند. شما باید شمارهی بازهها را به ترتیب صعودی بنویسید. در ضمن این شمارهها با فاصله از هم جدا کنید.
محدودیتها
ورودی و خروجی نمونه
ورودی نمونه | خروجی نمونه |
3 2
-1 1
2 3
-1 3 | 1
1 2 |
2 2
0 2
2 3 | 2
1 2 |