Unfoldung

펼치기(unfolding)는 다면체 표면 위의 최단 경로를 다루는 기법이다. 표면을 몇 개의 모서리를 따라 자른 뒤 각 면을 한 평면 위로 회전시켜 눕히면, 어려운 3차원 문제를 더 단순한 2차원 문제로 바꿀 수 있다. 이 문제에서는 주어진 물체의 표면을 지정된 모서리 집합을 따라 잘랐을 때, 그 표면을 하나의 평면 위로 펼칠 수 있는지 판정해야 한다.

물체는 단위 정육면체들을 면끼리 붙여 만든 입체의 바깥 표면이며, (정육면체가 하나뿐인 경우를 제외하면) 모든 정육면체는 적어도 하나의 다른 정육면체와 맞닿는다. 두 정육면체가 정확히 한 면을 공유하면 서로 인접한다고 한다. 우리는 바깥 표면만 살펴보므로(붙어서 안쪽에 숨은 면은 무시한다) 표면의 각 면은 단위 정사각형이고, 가정에 의해 표면의 모든 단위 모서리는 정확히 두 개의 표면 면과 맞닿는다.

표면은 그래프로 주어진다. 각 면이 정점이고, 나열된 각 단위 모서리는 그 모서리에서 만나는 두 면을 잇는다. 모든 모서리에는 자름 또는 안 자름 표시가 붙어 있다. 펼치기란 안 자른 모서리 하나를 골라 그 모서리를 축으로 한쪽 면을 돌려 두 면이 같은 평면에 놓이게(안쪽 이면각이 $180^\circ$가 되게) 만드는 일을 반복하는 것이다. 자른 모서리는 이미 떨어져 있으므로 회전축으로 쓰이지 않는다. 여러 면을 함께 돌려도 되고, 펼친 뒤의 평면 배치가 서로 겹쳐도 된다.

각 물체에 대해 다음 중 어느 경우인지 판정하라.

• 자른 모서리들 때문에 표면이 둘 이상의 조각으로 나뉜다(안 자른 모서리만으로는 서로 오갈 수 없는 면들이 생긴다).
• 표면이 한 조각이며 평평하게 펼칠 수 있다.
• 표면이 한 조각이지만 평평하게 펼칠 수 없다.

아래 그림은 두 정육면체를 붙인 물체의 바깥 표면을 평면 위로 펼치는 과정을 보여 준다. 점선은 안 자른 모서리, 실선은 자른 모서리다. 이 물체는 첫 번째 예제의 입력에 해당하며, 면 안의 숫자는 면 번호를 나타낸다.

첫 줄에 물체의 수 $t$ ($1 \le t \le 10$)가 주어진다. 각 물체는 다음과 같이 주어진다.

첫 줄에 바깥 표면의 면 개수 $f$ ($6 \le f \le 10000$)가 주어지며, 면은 $1$부터 $f$까지 번호가 매겨진다. 다음 줄에는 면 사이의 단위 모서리 개수 $n$이 주어지고, 이어서 정확히 $n$개의 줄이 온다. 각 줄은 x+y 또는 x-y 꼴의 문자열이며, $x$와 $y$는 공통 모서리에서 만나는 서로 다른 두 면의 번호($1 \le x, y \le f$)다. +는 그 모서리가 잘렸음을, -는 안 잘렸음을 뜻한다. 줄에는 공백이 없고, 빈 줄도 없다.

각 물체마다 한 줄을 출력한다. 표면을 평평하게 펼칠 수 있으면 CAN UNFOLD, 한 조각이지만 펼칠 수 없으면 CANNOT UNFOLD, 자른 모서리들이 표면을 둘 이상의 조각으로 나누면 DISCONNECTED를 출력한다. 표면이 나뉘어 있으면 각 조각을 펼칠 수 있는지와 관계없이 DISCONNECTED를 출력한다. 출력은 대소문자를 구분한다.