- محدودیت زمان: ۴ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
میلاد و پارسا که از رسیدن به مرحلهی نهایی کدکاپ ۳ جا ماندند، چشم و گوششان باز شد و به فکر کسب درآمد افتادند. برای کسب درآمد ابتدا به برجسازی فکر کردند؛ اما پس از اینکه دیدند سوال برجسازی از مسابقه شماره ۲ Quera را هنوز کسی حل نکرده متوجه شدند که برجسازی کار سختیست و برای انجام کاری سادهتر به فکر پلسازی افتادند!
میلاد و پارسا به اقیانوس اطلس رفتند و میخواهند طی یک پروژهی بزرگ پلسازی، مجمعالجزایرهای شکرآباد را همبند کنند! در شکرآباد $t$ مجمعالجزایر وجود دارد که باید همبند شود؛ یعنی از هریک از جزیرههای یک مجمعالجزایر باید بتوان با استفاده از پلهای ساخته شده به همهی جزیرههای آن مجمعالجزایر رفت. این مجمعالجزایرها کاملاً مستقل از هم فرض میشوند و هریک بصورت جدا باید همبند شود. هر یک از این مجمعالجزایرها شامل تعدادی جزیره است که هر جزیره در نقشه به شکل یک مستطیل است. مستطیلهای نشاندهندهی جزیرهها مجزا از هم هستند و با یکدیگر مساحت مشترک ندارند، البته میتوانند در ضلع با هم مشترک باشند. همچنین اضلاع این مستطیلها موازی با محورهای استوا و نصفالنهار مبدأ (محورهای مختصات!) است. برای همبند کردن این جزایر این دو پلساز با استفاده از ابزارآلات پیشرفته، میتوانند پلهایی بکشند که در راستای محورهای مختصات باشد. (دو جزیره که ضلع مشترک هم داشته باشد هم به هم متصل نیستند و باید بینشان پل کشید تا به هم متصل شود.) پلهای کشیده شده نباید با یکدیگر تقاطع داشته باشد، اما انتهای یک پل میتواند یک پل ساختهشدهی دیگر باشد. انتهای پلها میتواند ضلعهای جزیرهها، دریا و یا پلهای دیگر باشد، اما نمیتواند از روی یک جزیره و یا از روی ضلع یک جزیره به طور کامل رد شود. همچنین یک پل میتواند از یک جزیره شروع شود و در دریا تمام شود، یا حتی یک پل میتواند از دریا شروع شود و در دریا تمام شود!
حال میلاد و پارسا متوجه شدند که علیرغم تمام تلاششان، باز هم به مسئلهای برنامهنویسی برخوردند و سر به بیابان زده و این سوال را برای شما باقی گذاشتند. پس شما با ورودی گرفتن نقشهی هر مجمعالجزایر، کمترین تعداد پلهایی را بگویید که با وصل کردنشان طبق شرایط گفته شده تمام جزیرههای این مجمعالجزایر همبند شود.
یک مثال جهت وضوع بیشتر: در عکس زیر ۱۰ جزیرهی مستطیلی وجود دارد که با ۱۰ پل با هم همبند شدهاند که یکی از پاسخهای بهینه است.
ورودی
در اولین سطر ورودی یک عدد $t$ آمده است که نمایانگر تعداد مجمعالجزایرهای شکرستان است. سپس $t$ توضیح مجمعالجزایر آمده است. در هر یک از این توضیحات، ابتدا یک عدد $n$ آمدهاست که برابر تعداد جزیرههای این مجمعالجزایر است. سپس در هریک از $n$ سطر بعدی، ۴ عدد $x_1$ ، $y_1$ ، $x_2$ و $y_2$ آمدهاست که مختصات ۴ گوشهی مستطیل متناظر جزیره را نشان میدهند.
تضمین میشود مستطیلهای داده شده در شرایط صورت سوال صدق میکنند. دقت کنید که مجمعالجزایرها مستقل از هم هستند؛ یعنی ممکن است دو مستطیل از دو مجمعالجزایر مختلف با هم مساحت مشترک داشته باشند ولی در یک مجمعالجزایر هیچ دو مستطیلی با هم مساحت مشترک ندارند.
$$1 \le t \le 5$$ $$1 \le n \le 200\ 000$$ $$|x_1, x_2, y_1, y_2| \le 10^9$$ $$x_1 < x_2$$ $$y_1 < y_2$$
خروجی
در خروجی $t$ عدد چاپ کنید که پاسخ مسئله برای هر مجمعالجزایر است.
مثال
ورودی نمونه
3
2
1 1 2 2
3 2 4 3
5
1 1 2 2
3 2 4 3
5 3 6 4
5 4 6 5
7 7 8 8
6
1 1 2 2
3 2 4 3
5 3 6 4
5 4 6 5
1 7 6 8
9 9 10 10
خروجی نمونه
1
5
6
ارسال پاسخ برای این سؤال