+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در کشور کدکاپ $n$ شهر وجود دارد. شهرهای کدکاپ با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند. بین شهرهای کدکاپ تعدادی جاده قرار دارد. می‌دانیم هر جاده دو طرفه است و دقیقاً دو شهر مختلف را به هم متصل می‌کند. در واقع نقشه کشور کدکاپ، به‌صورت یک گراف ساده است. به سه شهر مختلف مثل $u$، $v$ و $w$ یک *مثلث* می‌گوییم، هرگاه بین $uv$، $vw$ و $uw$ یک جاده وجود داشته باشد.  نقشه‌ی کشور کدکاپ گم شده اما تعداد شهرهای آن یعنی $n$ را می‌دانیم. همچنین برای $m$ جفت از شهرها مثل $a_i$ و $b_i$ می‌دانیم شهر $a_i$ و شهر $b_i$ باهم در حداقل یک مثلث آمده‌اند. یعنی شهر دیگری مثل $c_i$ وجود دارد که این سه‌شهر باهم یک مثلث تشکیل می‌دهند. توجه کنید که مقدار $c_i$ را نداریم. همچنین برای $k$ جفت از شهر‌ها مثل $a_i$ و $b_i$ می‌دانیم در هیچ مثلثی نیامده‌اند. یعنی هیچ شهری مثل $c_i$ وجود ندارد که با آن‌ها تشکیل مثلث بدهد. حال از شما می‌خواهیم باتوجه به این اطلاعات بررسی کنید نقشه‌ی قابل قبولی برای کشور کدکاپ وجود دارد یا نه. همچنین در صورت وجود چنین کشوری، یک مثال از آن را ارائه کنید. # ورودی در سطر اول ورودی، عدد صحیح $t$ آمده که تعداد تست‌ها را نشان می‌دهد. $$1 \leq t \leq 1000$$ در سطر اول هر تست سه عدد $n$، $m$ و $k$ آمده است که به ترتیب تعداد شهرهای کدکاپ قدیم، تعداد جفت شهرهایی که در حداقل یک مثلث آمده‌اند و تعداد جفت شهرهایی که در هیچ مثلثی نیامده‌اند. $$1 \leq n \leq 1000, \quad 0 \leq m + k \leq \frac{n(n - 1)}{2}$$ در $m+k$ سطر بعدی، در هر سطر دو شهر $u$ و $v$ آمده که $m$ جفت اول در حداقل یک مثلث آمده‌اند و $k$ جفت آخر در هیچ مثلثی نیامده‌اند. $$1 \leq u \neq v \leq n$$ تضمین می‌شود که هر جفت شهر حداکثر یکبار بیاید. همچنین مجموع $n$ برای همه‌ی تست‌ها حداکثر ۱۰۰۰ باشد. # خروجی با عبارت `YES` و `NO` بگویید چنین گرافی وجود دارد یا نه. اگر جواب `YES` بود یک نقشه با شرایط گفته شده چاپ کنید. برای چاپ کردن نقشه، در سطر بعد از `YES` عدد $e$ را چاپ کنید که تعداد جاده‌های موجود را نشان می‌دهد. سپس در $e$ سطر بعدی در هر سطر دو عدد صحیح مثل $u$ و $v$ با یک فاصله از هم چاپ کنید که وجود یک جاده بین $u$ و $v$ را نشان می‌دهد. توجه کنید باید هر جاده را حداکثر یکبار چاپ کنید و هیچ جاده‌ای ابتدا و انتهای یکسانی نداشته باشند. اگر چند جواب برای مسئله وجود دارد، یکی را به دلخواه چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 4 3 0 0 3 1 0 2 1 3 2 0 1 2 3 1 3 1 2 2 1 3 1 2 3 ``` ## خروجی نمونه ۱ ``` YES 2 2 1 1 3 YES 3 1 2 3 1 3 2 YES 3 1 2 1 3 2 3 NO ```

حل سؤال در بانک سؤالات