Unfoldung

Unfolding is a technique for reasoning about shortest paths on the surface of a polyhedron: we cut the surface along some edges and rotate its faces onto a common plane, turning a hard 3D question into a simpler 2D one. In this problem you must decide whether the surface of a given object can be laid out onto a single plane when it is cut along a prescribed set of its edges.

The object is the outer surface of a solid built from unit cubes glued face to face, where every cube touches at least one other cube (unless the object is a single cube). Two cubes are adjacent when they share exactly one face. We consider only the outer surface (faces that are glued together and hidden inside are ignored), so every surface face is a unit square and, by assumption, every unit edge of the surface borders exactly two surface faces.

The surface is described as a graph: the faces are the nodes, and each listed unit edge joins the two faces that meet along it. Every edge is labeled either cut or uncut. Unfolding means repeatedly choosing an uncut edge and rotating one of its two faces about that edge until the two faces become coplanar (the interior dihedral angle becomes $180^\circ$). Cut edges are already separated and are never used as hinges. Several faces may be rotated together, and the resulting flat layout is allowed to overlap itself.

For each object decide which of the following holds:

• The cut edges split the surface into two or more disconnected pieces (there are faces that cannot reach one another through uncut edges).
• The surface is a single piece and can be unfolded flat.
• The surface is a single piece but cannot be unfolded flat.

The figure below shows the outer surface of two glued cubes being unfolded onto a plane; dotted edges are uncut and solid edges are cut. This object is exactly the first example test case, and the numbers inside the faces identify them.

The first line contains an integer $t$ ($1 \le t \le 10$), the number of objects. Each object is given as follows.

The first line contains an integer $f$ ($6 \le f \le 10000$), the number of faces of the outer surface; the faces are numbered from $1$ to $f$. The next line contains an integer $n$, the number of unit edges between faces, followed by exactly $n$ lines. Each of those lines is a string of the form x+y or x-y, where $x$ and $y$ are distinct integers ($1 \le x, y \le f$) naming two faces that meet along a common edge. A + sign means that edge is cut; a - sign means it is uncut. Lines contain no spaces, and there are no blank lines.

For each object print one line. Print CAN UNFOLD if the surface can be unfolded flat, CANNOT UNFOLD if it is a single piece that cannot be unfolded, and DISCONNECTED if the cut edges separate the surface into two or more pieces. If the surface is disconnected, print DISCONNECTED regardless of whether the individual pieces could otherwise be unfolded. The output is case sensitive.