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

---

ایران‌سرور (IranServer) تصمیم گرفته که برای رونمایی از خدمات جدید خود، یک جلسه مهم میزگردی با حضور مشتری‌های کلیدی‌اش برگزار کند. هدف این جلسه، بحث و بررسی درباره نیازها و تجربه‌های مشتریان است تا تیم ایران‌سرور بتواند خدماتش را بهینه‌تر کند.

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

ایران‌سرور می‌خواهد مشتری‌ها را به شکلی روی دو میز تقسیم کند که:

1. هیچ دو نفری که آشنا هستند، روی یک میز نباشند.
2. تعداد افراد روی دو میز باید تا حد امکان متعادل باشد تا هر دو میز فرصت برابری برای بحث‌های مفید داشته باشند. (منظور از متعادل این است که اختلاف تعداد افراد روی دو میز کمترین مقدار ممکن باشد!)

جزئیات پروژه

پروژه‌ی اولیه را از این لینک دانلود کنید.

تابع iranServerRoundTable را طوری کامل کنید که خروجی خواسته شده را برگرداند:

<?php

function iranServerRoundTable(int $n, int $m, array $connections): string {
    // TODO
}

ورودی تابع:

• مقدار n، نشان‌دهنده تعداد افراد حاضر در مهمانی است.
• مقدار m، نشان‌دهنده تعداد آشنایی‌های قبلی که میان افراد وجود دارد، است.
• مقدار connections، لیستی از m آشنایی‌ که هر یک به صورت یک جفت مانند [A, B] است که نشان دهنده وجود آشنایی قبلی میان دو فرد A و B است.

خروجی تابع:

• در صورتی که امکان تقسیم‌بندی افراد بین دو میز مطابق شرایط داده شده وجود داشته باشد، یک آرایه که در آن مقدار کلید possible برابر با "YES" و دو کلید table_1 و table_2 که نشان‌دهنده لیستی از افراد دور هر میز هستند را بازگرداندید.
• در غیر این صورت، آرایه‌ای شامل کلید possible با مقدار "NO" بازگرداندید.
• در نهایت خروجی برنامه‌ی شما باید به فرمت JSON باشد.

نکته

مقدار کلید possible در هر یک از شرایط ذکر شده، باید دقیقا به شکلی که نوشته شده است باشد. (بزرگی و کوچکی حروف مهم است!)

توجه: این سؤال از نوع ساختاری (Constructive) است، بنابراین پاسخ‌های ممکن لزوماً یکتا نیستند. با این حال، سیستم داوری پاسخ‌های شما را بررسی می‌کند تا اطمینان حاصل شود که شرایط مسئله به‌درستی رعایت شده‌اند. تنها در صورتی نمره دریافت خواهید کرد که پیاده‌سازی شما تمامی این شرایط را برآورده کند و یکی از پاسخ‌های معتبر مسئله باشد.

مثال‌ها

نمونه ورودی ۱:

>>  iranServerRoundTable(6, 6, [
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 5],
        [5, 6],
        [6, 1],
    ]);

نمونه خروجی ۱:

{
    "possible": "YES",
    "table_1": [1, 3, 5],
    "table_2": [2, 4, 6],
}

توضیحات نمونه

این مثال شامل ۶ نفر است که هر یک از آن‌ها دقیقا با دو فرد دیگر آشنایی قبلی دارد؛ به شکل زیر توجه کنید:

حال می‌توانیم آن‌ها را به صوزت زیر به دو گروه مجزا تقسیم بندی کرد:

$$ Table_1 : [1, 3, 5], Table_2 : [2, 4, 6] $$

نمونه ورودی ۲:

>>  iranServerRoundTable(6, 5, [
        [1, 2],
        [3, 4],
        [3, 5],
        [4, 5],
        [1, 6],
    ]);

نمونه خروجی ۲:

{
    "possible": "NO"
}

توضیحات نمونه

این مثال شامل ۶ نفر است و رابط آشنایی میان‌ آن‌ها به شکل زیر است:

در این مثال نمی‌توان افراد را طوری برا سر دو میز نشاند که شرایط خواسته شده را حفظ کند؛ چرا که در تصویر زیر فرد شماره ۵ را نمی‌توان دور هیچ‌یک از میزها نشاند!

نمونه ورودی ۳:

>>  iranServerRoundTable(6, 3, [
        [1, 2],
        [3, 4],
        [3, 5],
    ]);

نمونه خروجی ۳:

{
    "possible": "YES",
    "table_1": [1, 4, 5],
    "table_2": [2, 3, 6],
}

توضیحات نمونه

این مثال شامل ۶ نفر است و رابط آشنایی میان‌ آن‌ها به شکل زیر است:

یکی از حالات مطلوب جهت تقسیم افراد به دو میز موجود به شکل زیر است:

حالت دیگری هم وجود دارد که می‌توان این کار را انجام داد اما با شرط دوم (متعادل بودن میز‌ها) را ندارد!

تصویر زیر یکی از حالاتی است که برای این مسئله موردقبول نیست:

آن‌چه باید آپلود کنید

یک فایل PHP با نام solution.php که تابع iranServerRoundTable در آن پیاده‌سازی شده است آپلود کنید.