Магічні графи
Граф називається k-частковим, якщо його вершини можна розділити на K неперетинні множини так, що жодні дві вершини в одній множині не є суміжними. У цій задачі ми розглядаємо особливий випадок k-часткового графа, де кожна неперетинна множина містить рівно дві вершини. Такий граф ми називаємо магічним графом. Далі ми дамо характеристику таких магічних графів.
Нехай P — це множина позитивних міток {1, 2, 3, 4, …}, а N — множина негативних міток {1', 2', 3', 4',…}. Також нехай L = P U N. Магічний граф — це k-частковий граф G = (V, E), де V — множина вершин, а E — множина ребер. Ми визначаємо V = V_1 U V_2 U V_3 U … U V_k, де кожна V_i є підмножиною L і |V_i| = 2. Існує ребро {l_1, l_2} в G тоді і тільки тоді, коли l_1 і l_2 належать до різних множин вершин і l_1 і l_2 не є позитивною та негативною мітками одного і того ж числа. Наприклад, наступний граф є магічним графом.
Цей граф є тричастковим магічним графом. V_1 — це {1, 2}. V_2 — це {1', 2'}. V_3 — це {1, 2'}. Зверніть увагу, що кілька вузлів можуть мати однакову мітку. Наприклад, вузол з міткою 1 в V_1 не є тим самим вузлом, що і вузол з міткою 1 в V_3. Ребра дотримуються вищезазначеного правила. Наприклад, існують ребра {1, 1} і {1, 2'}, оскільки мітки знаходяться в різних множинах вершин і не є позитивною та негативною мітками одного і того ж числа. Зверніть увагу, що ребро {1, 1'} не існує, оскільки дві мітки є позитивною та негативною мітками одного і того ж числа.
Дано k-частковий магічний граф G, ваше завдання — визначити, чи існує в G k-кліка.
Вхідні дані
Перша строка введення містить кількість тестових випадків T ≤ 10. Формат кожного тестового випадку наступний.
Перша строка містить ціле число K (2 ≤ K ≤ 24000).
Наступні K рядків описують множину V_i, по одному на рядок. Для кожного рядка є дві мітки, розділені пробілом. Позитивна мітка представлена додатним числом, а негативна мітка — знаком мінус і додатним числом.
Вихідні дані
Вихідний файл містить лише один рядок довжини T у {Y, N}*. Тобто, для кожного тестового випадку, якщо даний магічний граф G має k-кліку, виведіть Y, інакше виведіть N.