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

در یک ردیف 2n2n نفر روی صندلی نشسته‌اند، این 2n2n نفر شامل دقیقاً nn زوج (زن و شوهر) هستند. حال می‌خواهیم یکبار دو نفر را انتخاب کنیم و از آن‌ها خواهش کنیم که جایشان را باهم عوض کنند. به طوری که بعد از آن هر کس کنار همسر خودش نشسته باشد. بررسی کنید آیا این کار شدنی است یا نه؟

ورودی

در سطر اول ورودی، عدد صحیح و مثبت tt آمده است که تعداد سناریوها را نشان می‌دهد. 1t100,0001 \leq t \leq 100 , 000

در سطر اول هر سناریو عدد صحیح و مثبت nn آمده است که تعداد زوج‌ها را نشان می‌دهد. 1n100,0001 \leq n \leq 100 , 000

در سطر دوم هر سناریو، 2n2n رشته آمده که رشته‌ی iiام وضعیت نفر iiام در صف را نشان می‌دهد. هر وضعیت به فرمت یک کاراکتر و یک عدد است که کاراکتر اول W (زن) یا M (مرد) بوده و عدد بعد از آن شماره‌ی زوج را نشان می‌دهد. زوج‌ها با 11 تا nn شماره گذاری می‌شوند.

تضمین می‌شود در هر سناریو ورودی شامل همه‌ی 2n2n نفر باشد. همچنین تضمین می‌شود مجموع nnها برای همه‌ی tt سناریو حداکثر ۱۰۰،۰۰۰ باشد.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ‌ ۳۰ n500\sum n \leq 500
۲ ۷۰ بدون محدودیت اضافی

خروجی

در tt سطر در صورتی که می‌توان با یک جابه‌جایی زوج‌ها کنار هم گذاشت، YES و در غیر این‌صورت NO چاپ کنید.

مثال

ورودی نمونه ۱

3
1
M1 W1
4
W1 M1 W4 M2 W3 M3 M4 W2
3
W1 W2 W3 M1 M2 M3
Plain text

خروجی نمونه ۱

YES
YES
NO
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.