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