- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک مهمانی $n$ مهمان حضور دارند. مهمانان این مهمانی کمی عجیب‌وغریب هستند و هر مهمان تنها با مهمانانی که قد یا وزنشان دقیقاً برابر با اوست حرف می‌زند! به یک مهمانی بد می‌گوییم اگر مهمان‌ها را بتوان به دو گروه تقسیم کرد، به طوری که هیچ کسی از گروه اول نتواند با هیچ فردی از گروه دوم حرف بزند. میزبان می‌خواهد تعدادی مهمان جدید دعوت کند که مهمانی دیگر بد نباشد.
مثلاً اگر مهمانی فقط شامل دو مهمان یکی با قد ۱۵۰ سانتی‌متر و وزن ۷۰ کیلوگرم، و دیگری با قد ۱۸۰ سانتی‌متر و وزن ۹۰ کیلوگرم باشد، این دو مهمان نمی‌توانند با هم صحبت کنند و بنابراین مهمانی بد است. با این حال اگر یک فرد با قد ۱۵۰ سانتی‌متر، و وزن ۹۰ کیلوگرم به مهمانی اضافه کنیم، مهمان جدید با هر دو مهمان قبلی می‌تواند صحبت کند و مهمانی دیگر بد نیست.
میزبان آشنایان خیلی زیادی دارد، در نتیجه با هر قد و وزنی که بخواهد می‌تواند مهمان دعوت کند. میزبان باید حداقل چند میهمان جدید دعوت کند که میهمانی بد نباشد؟
ورودی
در سطر اول ورودی، عدد صحیح و مثبت $n$ که نشان دهنده‌ی تعداد مهمانان اولیه است داده می‌شود. $$1 \leq n \leq 300 , 000$$
در هر کدام از $n$ سطر بعدی، در سطر $i$ام $h_i$ و $w_i$ که نشان دهنده‌ی قد و وزن مهمان $i$ام است داده می‌شود. $$1 \leq h_i, w_i \leq 300 , 000$$
خروجی
حداقل تعداد مهمان جدیدی که میزبان باید دعوت کند، تا مهمانی بد نباشد را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
2
150 70
180 90
خروجی نمونه ۱
1
توضیح نمونه ۱
این مثال در متن سوال توضیح داده شده است.
ورودی نمونه ۲
3
1 3
1 9
2 4
خروجی نمونه ۲
1
توضیح نمونه ۲
اگر مهمانی با قد ۱ و وزن ۴ به مهمانی اضافه شود، دیگر مهمانی بد نیست.
ورودی نمونه ۳
4
1 3
7 3
2 5
1 5
خروجی نمونه ۳
0
توضیح نمونه ۳
مهمانی همین الان هم بد نیست!
ارسال پاسخ برای این سؤال