روی محور اعداد $n$ بازه‌ی بسته به شما داده شده است. یک رنگ‌آمیزی از بازه‌ها معتبر است اگر هیچ دو بازه‌ی ﻫﻤﺮﻧﮕﯽ ﺍﺷﺘﺮﺍﮎ ﻧﺪﺍﺷﺘﻪ ﺑﺎﺷﻨﺪ (ﺩﻭ ﺑﺎﺯﻩ ﺍﺷﺘﺮﺍﮎ ﺩﺍﺭﻧﺪ ﺍﮔﺮ ﺩﺭ ﺣﺪﺍﻗﻞ ﯾﮏ ﻧﻘﻄﻪ ﻣﺸﺘﺮﮎ ﺑﺎﺷﻨﺪ). ﯾﮏ ﻋﺪﺩ $x$ ﺑﻪ ﺷﻤﺎ ﺩﺍﺩﻩ ﻣﯽﺷﻮﺩ، ﺷﻤﺎ ﺑﺎﯾﺴﺘﯽ $x$ ﺗﺎ ﺍﺯ ﺍﯾﻦ $n$ ﺑﺎﺯﻩ ﺭﺍ ﺍﻧﺘﺨﺎﺏ ﮐﻨﯿﺪ ﻃﻮﺭﯼ ﮐﻪ ﺑﺘﻮﺍﻥ ﺑﺎ ﮐﻤﺘﺮﯾﻦ ﺗﻌﺪﺍﺩ ﺭﻧﮓ، ﯾﮏ ﺭﻧﮓﺁﻣﯿﺰﯼ ﻣﻌﺘﺒﺮ ﺑﺮﺍﯼ ﺁﻧﻬﺎ ﺍﺭﺍﺋﻪ ﮐﺮﺩ.

ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:

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

ﺩﺭ ﺳﻄﺮ ﻧﺨﺴﺖ ﻭﺭﻭﺩﯼ ﺩﻭ ﻋﺪﺩ ﺻﺤﯿﺢ $n$ و $x$ به ترتیب نوشته شده‌اند.($1\leq n \leq 10^5$ و $1\leq x \leq n$)

در $n$ سطر بعد مشخصات $n$ بازه آمده است. در سطر $i+1$ام دو عدد نوشته شده است که به ترتیب ابتدا و انتهای بازه‌ی $i$ ام را مشخص می‌کنند.(تمام اعداد ورودی در بازه‌ی $[-2^{30},2^{30}]$ می‌باشند.

ﺩﺭ ﺳ‰ﻄ‰ﺮ ﻧ‰ﺨ‰ﺴ‰ﺖ ﺧ‰ﺮﻭﺟ‰ﯽ کم‌ترین ﺗ‰ﻌ‰ﺪﺍﺩ ﺭﻧ‰ﮓ ﻻﺯﻡ ﺑ‰ﺮﺍﯼ ﺭﻧ‰ﮓ ﺁﻣ‰ﯿ‰ﺰﯼ ﻣ‰ﻌ‰ﺘ‰ﺒ‰ﺮ $x$ ﺑ‰ﺎﺯﻩﯼ ﺍﻧﺘﺨﺎﺑﯽ ﺭﺍ ﺑﻨﻮﯾﺴﯿﺪ.

ﺩﺭ ﺳﻄﺮ ﺩﻭﻡ $x$ ﻋﺪﺩ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ ﺷﻤﺎﺭﻩﯼ ﺑﺎﺯﻩﻫﺎﯼ ﺍﻧﺘﺨﺎﺑﯽ ﺭﺍ مشخص ﻣﯽﮐﻨﺪ. ﺷﻤﺎ ﺑﺎﯾﺪ ﺷﻤﺎﺭﻩﯼ ﺑﺎﺯﻩﻫﺎ ﺭﺍ ﺑﻪ ﺗﺮﺗﯿﺐ ﺻﻌﻮﺩﯼ ﺑﻨﻮﯾﺴﯿﺪ. ﺩﺭ ﺿﻤﻦ ﺍﯾﻦ ﺷﻤﺎﺭﻩﻫﺎ ﺭﺍ ﺑﺎ ﻓﺎﺻﻠﻪ ﺍﺯ ﻫﻢ ﺟﺪﺍ ﮐﻨﯿﺪ.

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

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