Unfoldung#6843
Рамтунг, старший докторант, повинен запропонувати задачу для цьогорічного конкурсу з програмування ACM. Оскільки він повністю занурений у свої дослідження, він не може думати про щось поза своєю науковою галуззю — найкоротші шляхи в обчислювальній геометрії.
Однією з задач у цій галузі є знаходження найкоротшого шляху між двома заданими точками на поверхні многогранника. Метод, який допомагає знаходити такі шляхи, називається розгортка. Ми розрізаємо поверхню многогранника вздовж деяких відрізків так, щоб її можна було розгорнути на площину. Ця плоска поверхня дозволяє застосовувати простіші методи для знаходження потрібного шляху. У задачі розгортки (названій на честь її автора, Рамтунга) вам потрібно визначити, чи можна розгорнути поверхню даного многогранника на площину, розрізавши її вздовж деяких його ребер.
Щоб спростити завдання, ми розглядаємо як вхідні дані зовнішню поверхню твердого об'єкта, що складається з одиничних кубів, склеєних один з одним своїми гранями так, що кожен куб прилягає принаймні до одного іншого куба (якщо об'єкт не складається з одного куба). Ми кажемо, що два куби є суміжними, якщо вони мають рівно одну спільну грань. Ми хочемо розгорнути зовнішню поверхню об'єкта (тобто ігноруємо грані, що склеєні) для отримання плоского розгортання. Вхідними даними задачі є опис зовнішньої поверхні, а також ряд одиничних ребер поверхні, які потрібно розрізати. Для спрощення можна припустити, що даний об'єкт є таким, що кожне ребро зовнішньої поверхні прилягає рівно до двох граней зовнішньої поверхні.
Наприклад, Рис. а і Рис. б показують, як зовнішня поверхня двох склеєних кубів розгортається на площину. На Рис. а пунктирні ребра не розрізані, а суцільні лінії показують ті, що розрізані. Зверніть увагу, що грань efgh не є частиною зовнішньої поверхні. Вхідні дані до цього прикладу наведені в першому прикладі вхідних даних. (Числа всередині граней правого розгортання (Рис. б) використовуються для ідентифікації граней у прикладі вхідних даних.)
Вам потрібно написати програму, щоб визначити, чи може така поверхня бути розкладена на площину після розгортання її граней. Під розгортанням ми маємо на увазі обертання грані навколо одного з її ребер до тих пір, поки вона не стане компланарною з іншою гранню, суміжною з цим ребром (так що кут між гранями всередині поверхні становитиме 180^\circ). Зверніть увагу, що можливо, щоб розкладка, отримана після розгортання, перекривалася. Якщо можливо, можна обертати більше ніж одну грань одночасно.
Перший рядок вхідного файлу містить одне ціле число (1 \le t \le 10), кількість тестових випадків, за яким йдуть вхідні дані для кожного тестового випадку. Перший рядок кожного тестового випадку містить одне ціле число (6 \le f \le 10000), яке є кількістю граней на зовнішній поверхні. Припустимо, що грані пронумеровані унікально від до . Другий рядок містить ціле число , яке є кількістю одиничних ребер між гранями зовнішньої поверхні, за яким йдуть рівно рядків, кожен з яких містить рядок у формі x+y або x-y. та — це різні цілі числа (1 \le x, y \le f), що представляють дві грані поверхні. Обидві форми вказують, що грань суміжна з гранню вздовж спільного ребра. Знак плюс показує, що ребро, спільне для і , розрізане (суцільні лінії на Рис. а), а знак мінус вказує, що ребро не розрізане (пунктирні лінії). У рядку немає пробілів, і у вхідних даних немає порожніх рядків.
Для кожного тестового випадку має бути один рядок, що містить рядок, який вказує на результат для тестового випадку. Вивід має бути рядком CAN UNFOLD, якщо можна розгорнути дану поверхню, CANNOT UNFOLD, якщо поверхню не можна розгорнути, і DISCONNECTED, якщо поверхня розділена на дві або більше частин розрізаними ребрами. Зверніть увагу, що якщо поверхня роз'єднана, ваш вивід має бути DISCONNECTED незалежно від того, чи можна її розгорнути чи ні. Будьте уважні, вивід є чутливим до регістру.
Приклад 1