- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شرکت تخریبگران محیط زیست مسئول هموار کردن شهرها جهت سهولت در حمل و نقل شده. بدین منظور آنها میخواهند در همه کوههای شهر تونل حفر کنند تا شهر هموار شود. به طور دقیقتر میتوان شهر را به صورت یک جدول با میلیارد سطر و ستون نشان داد که در برخی از خانههای آن کوه واقع شده است. این شرکت به تازگی یک بولدوزر قوی خریده است. بولدوزر میتواند در یک حرکت سطری در تمام کوههای یک سطر تونل بکند، به طور مشابه در یک حرکت ستونی میتواند در تمام کوههای یک ستون تونل حفر کند. به این شرکت کمک کنید که آیا هر شهر را با دقیقا یک حرکت سطری و یک حرکت ستونی بولدوزر میتوان هموار کرد؟
ورودی
در خط اول ورودی \(t\) تعداد شهرهای مورد برسی میآید سپس اطلاعات \(t\) شهر در خطوط بعد به ترتیب جداگانه میآید.
در خط اول اطلاعات شهر \(i\)، \(m_i\) تعداد کوههای شهر میآید و سپس در خط \(j\) از \(m_i\) خط بعد دو عدد \(x_{ij}\) شماره سطر کوه \(j\) و \(y_{ij}\) شماره ستون آن میآید. تضمین میشود کوههای یک شهر در نقاط متمایز دادهشوند.
\[t \le 12 \, 000\] \[\sum_{i=1}^t m_i \le 300 \, 000\] \[1 \le x_{ij}, y_{ij} \le 10^9\]
خروجی
برای هر شهر به ترتیب اگر با دقیقا یک حرکت سطری و یک حرکت ستونی هموارشدنی بود
YES وگرنه NO را خروجی دهید.
مثال
ورودی نمونه ۱
4
3
1 1
1 2
1 3
5
1 1
1 3
2 2
3 1
3 3
4
1 4
2 4
3 4
4 4
4
1 2
2 1
2 3
3 2
خروجی نمونه ۱
YES
NO
YES
YES
در شهر اول، کافی است کوههای سطر اول و ستون حفر شوند.
میتوان نشان داد که در شهر دوم عملیات مورد نیاز شرکت ممکن نیست.
در شهر سوم، شرکت میتواند کوههای سطر سوم و ستون چهارم را حفر کند.
نهایتا در شهر چهارم، تخریبگران میتوانند کوههای سطر و ستون دوم را حفر کنند تا به هدف خود برسند.