- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک ردیف \(2n\) نفر روی صندلی نشستهاند، این \(2n\) نفر شامل دقیقاً \(n\) زوج (زن و شوهر) هستند. حال میخواهیم یکبار دو نفر را انتخاب کنیم و از آنها خواهش کنیم که جایشان را باهم عوض کنند. به طوری که بعد از آن هر کس کنار همسر خودش نشسته باشد. بررسی کنید آیا این کار شدنی است یا نه؟
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(t\) آمده است که تعداد سناریوها را نشان میدهد. \[1 \leq t \leq 100 \, 000\]
در سطر اول هر سناریو عدد صحیح و مثبت \(n\) آمده است که تعداد زوجها را نشان میدهد. \[1 \leq n \leq 100 \, 000\]
در سطر دوم هر سناریو، \(2n\) رشته آمده که رشتهی \(i\)ام وضعیت نفر \(i\)ام در صف را نشان میدهد. هر وضعیت به فرمت یک کاراکتر و یک عدد است که کاراکتر اول W (زن) یا M (مرد) بوده و عدد بعد از آن شمارهی زوج را نشان میدهد. زوجها با \(1\) تا \(n\) شماره گذاری میشوند.
تضمین میشود در هر سناریو ورودی شامل همهی \(2n\) نفر باشد. همچنین تضمین میشود مجموع \(n\)ها برای همهی \(t\) سناریو حداکثر ۱۰۰،۰۰۰ باشد.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۳۰ | \(\sum n \leq 500\) |
| ۲ | ۷۰ | بدون محدودیت اضافی |
خروجی
در \(t\) سطر در صورتی که میتوان با یک جابهجایی زوجها کنار هم گذاشت، YES و در غیر اینصورت NO چاپ کنید.
مثال
ورودی نمونه ۱
3
1
M1 W1
4
W1 M1 W4 M2 W3 M3 M4 W2
3
W1 W2 W3 M1 M2 M3
خروجی نمونه ۱
YES
YES
NO