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 независимо от того, можно ли её развернуть или нет. Будьте внимательны, вывод чувствителен к регистру.