====== 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$
  * گراف یال چندگانه ندارد.
===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|1 \\ 5 13 \\ 0 0 \\ 0 1 \\ 0 2 \\ 0 3 \\ 0 4 \\ 1 1 \\ 1 0 \\ 2 2 \\ 3 3 \\ 3 0 \\ 4 0 \\ 4 4 \\ 2 0|1|

</WRAP>


  * [[سوال ۷|سوال بعد]]
  * [[سوال ۵|سوال قبل]]