احمد و عماد جدیدا الگوریتم مسئله‌ی دو ارضاپذیری را یاد گرفته‌اند. آن‌ها برای درک بیش‌تر مسئله، یک بازی به صورت زیر طراحی کرده‌اند: قبل از شروع بازی، ابتدا آن‌ها با هم‌فکری یکدیگر یک عبارت به فرم زیر می‌نویسند:

$$(a_1 \vee b_1) \wedge (a_2 \vee b_2) \wedge … \wedge (a_m \vee b_m)$$

به طوری که:

$$a_i,b_i \in \{x_1,x_2,…,x_n,\overline{x}_1,\overline{x}_2,…,\overline{x}_n \}(1\leq i \leq m)$$

سپس آن‌ها $n$ بار سکه می‌اندازند تا مشخص شود که هر کدام باید مقدار کادم متغیر‌ها را مشخص کنند. بعد از مشخص شدن نوبت‌ها، متغیرها به ترتیب از $x_1$ تا $x_n$ مقداردهی می‌شوند. هدف عماد این است که مقدار عبارت ۱ شود، در حالی که هدف احمد ۰ شدن عبارت است. با این فرض که هر دوی آن‌ها بهترین بازی خود را انجام می‌دهند، آیا عماد می‌تواند به هدفش برسد؟

در سطر اول ورودی عدد طبیعی $q$، تعداد سناریوها، آمده است. سپس $q$ بازی مختلف به فرمت زیر آمده‌اند.($1\leq q \leq 30$)

در سطر اول هر سناریو، دو عدد طبیعی $n$، تعداد متغیر‌ها و $m$، تعداد گزاره‌ها، آمده است.($1\leq n \leq 10^5$ و $1\leq m \leq 3 \times 10^5$)

در سطر دوم شامل رشته‌ی $t_1 t_2…t_n$ است به طوری که $t_i \in \{’A’ ,’E’ \}$. در صورتی که $t_i =’E’$ باشد، متغیر $i$- ام توسط عماد و در صورتی که $t_i=’A’$ باشد، توسط احمد مقداردهی می‌شود.

در هر یک از $m$ سطر بعدی دو عدد $a$ و $b$ آمده است که نشان‌دهنده‌ی یکی از متغیرهای $x_1,x_2,…,x_n,\overline{x}_1,\overline{x}_2,…,\overline{x}_n$ هستند. در صورتی که ($1\leq a \leq n$)، منظور متغیر $x_a$ و در صورتی که ($-n\leq a \leq -1$)، منظور متغیر $\overline{x}_{-a}$ است. معنای متغیر $b$ نیز به همین صورت است.

خروجی باید شامل $q$ سطر باشد که در سطر $i$- ام از آن‌ عبارت Yes چاپ می‌شود اگر عماد در سناریوی $i$- ام می‌تواند مقدار عبارت را برابر با ۱ کند و در غیر این صورت No چاپ می‌شود.

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

• سوال بعد
• سوال قبل