Taraneh

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

با تلاش شبانه‌روزی دانشمندان، الگوریتم متفاوتی برای رمزگشایی نامه‌ها به دست آمد که برای رمزگشایی نامه تنها به باقی‌مانده‌ی کلید نامه بر $4$ نیاز دارد. شما باید به باستان‌شناسان کمک کنید که باقی‌مانده‌ی کلید نامه بر $4$ را محاسبه کنند.

در این سوال شما باید تابع زیر را پیاده‌سازی کنید.

• int findKey(int n, int m, int *u, int *v)

این تابع $t$ بار فراخوانی می‌شود. تابع را طوری پیاده‌سازی کنید که با ورودی گرفتن گراف انتهای یک نامه، باقی‌مانده‌ی کلید آن نامه بر $4$ را مشخص کند.

• $n$: گراف $n$ راس قرمز و $n$ راس آبی دارد. رئوس هر رنگ به طور مجزا با اعداد $0$ تا $n - 1$ شماره‌گذاری شده‌اند.
• $m$: تعداد یال‌های گراف انتهای نامه
• $u, v$: دو آرایه به طول $m$. به ازای هر $i$ $(0 \le i \le m - 1)$ یک یال بین راس قرمز با شماره‌ی $u_i$ و راس آبی با شماره‌ی $v_i$ وجود دارد.

ارزیاب نمونه ورودی را به صورت زیر می‌خواند: در خط اول عدد $t$، تعداد موارد آزمون آمده است. سپس به ازای هر مورد آزمون، در یک خط دو عدد $n$ و $m$ آمده است. در هر یک از $m$ خط بعد، دو عدد آمده است که عدد خط $i$ ام $u_{i - 1}$ و $v_{i - 1}$ است.

• زیرمسئله‌ی اول (۲۹ نمره): حداقل یکی از مولفه‌های گراف با $C_4$ یک‌ریخت است.
• زیرمسئله‌ی دوم (۲۹ نمره): حداقل دو راس از یک بخش وجود دارند که مجموعه‌ی رئوس همسایه‌ی آن‌ها یکسان است.
• زیرمسئله‌ی سوم (۴۲ نمره): بدون محدودیت اضافی.

• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le t \le 10$
• $1 \le n \le 50$
• $0 \le m \le n^2$
• $0 \le u_i, v_i \le n - 1$
• گراف یال چندگانه ندارد.

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