مهمانی بد


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

در یک مهمانی nn مهمان حضور دارند. مهمانان این مهمانی کمی عجیب‌وغریب هستند و هر مهمان تنها با مهمانانی که قد یا وزنشان دقیقاً برابر با اوست حرف می‌زند! به یک مهمانی بد می‌گوییم اگر مهمان‌ها را بتوان به دو گروه تقسیم کرد، به طوری که هیچ کسی از گروه اول نتواند با هیچ فردی از گروه دوم حرف بزند. میزبان می‌خواهد تعدادی مهمان جدید دعوت کند که مهمانی دیگر بد نباشد.

مثلاً اگر مهمانی فقط شامل دو مهمان یکی با قد ۱۵۰ سانتی‌متر و وزن ۷۰ کیلوگرم، و دیگری با قد ۱۸۰ سانتی‌متر و وزن ۹۰ کیلوگرم باشد، این دو مهمان نمی‌توانند با هم صحبت کنند و بنابراین مهمانی بد است. با این حال اگر یک فرد با قد ۱۵۰ سانتی‌متر، و وزن ۹۰ کیلوگرم به مهمانی اضافه کنیم، مهمان جدید با هر دو مهمان قبلی می‌تواند صحبت کند و مهمانی دیگر بد نیست.

میزبان آشنایان خیلی زیادی دارد، در نتیجه با هر قد و وزنی که بخواهد می‌تواند مهمان دعوت کند. میزبان باید حداقل چند میهمان جدید دعوت کند که میهمانی بد نباشد؟

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت nn که نشان دهنده‌ی تعداد مهمانان اولیه است داده می‌شود. 1n3000001 \leq n \leq 300 \, 000

در هر کدام از nn سطر بعدی، در سطر iiام hih_i و wiw_i که نشان دهنده‌ی قد و وزن مهمان iiام است داده می‌شود. 1hi,wi3000001 \leq h_i, w_i \leq 300 \, 000

خروجی🔗

حداقل تعداد مهمان جدیدی که میزبان باید دعوت کند، تا مهمانی بد نباشد را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

2
150 70
180 90
Plain text

خروجی نمونه ۱🔗

1
Plain text
توضیح نمونه ۱

این مثال در متن سوال توضیح داده شده است.


ورودی نمونه ۲🔗

3
1 3
1 9
2 4
Plain text

خروجی نمونه ۲🔗

1
Plain text
توضیح نمونه ۲

اگر مهمانی با قد ۱ و وزن ۴ به مهمانی اضافه شود، دیگر مهمانی بد نیست.


ورودی نمونه ۳🔗

4
1 3
7 3
2 5
1 5
Plain text

خروجی نمونه ۳🔗

0
Plain text
توضیح نمونه ۳

مهمانی همین الان هم بد نیست!