本题没有可用的提交语言。

题目描述

在许多几何书籍中可以找到诸如立方体或八面体等立体的展开图，但如果不实际折叠，很难判断这些构造是否真的可行。在本问题中，我们将考虑一类特殊的展开图。

给定一个由平面上的单位正方形组成的展开图，以及关于沿哪些边以何种方向折叠的描述，判断该展开图是否能折叠成一个三维空间中的闭合立体表面。如果可以，求出该立体的体积。

具体来说，展开图由平面上一个连通的单位正方形集合组成。对于任意两个相连正方形的边，你需要根据给定的描述决定是否沿该边向前、向后（始终以直角）折叠或不折叠。如果展开图中两个相邻正方形之间的边未在输入中提及，则可以认为这两个正方形不相连，在折叠时可以撕开。然而，相连的边必须始终按照描述进行折叠。

对于我们的目的，闭合表面是指展开图中的每个正方形都将内部与外部隔开。折叠后，展开图中的正方形位于三维矩形网格上，每个正方形将一个内部单元（边长为1单位的立方体）与一个外部单元隔开。对于每个单元，必须明确其位于内部还是外部。以下示意图在二维中说明了这一规则：

注意，即使第二个展开图也满足我们对闭合表面的定义，但其内部并不连通。

两个不同的正方形在空间中不能占据完全相同的位置，尽管它们可能在边和顶点处接触（对于闭合表面来说是必然的）。确保展开图不会通过相连的边自相交。除此之外，无需担心折叠过程，例如哪些边先折叠或结构的一部分是否阻碍其他部分。

输入格式

输入文件包含多个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $e$。其中 $n$（$1 \leq n \leq 200$）表示展开图中正方形的数量，$e$（$0 \leq e \leq 300$）表示边的数量。正方形的编号为 $0$ 到 $n-1$。接下来的 $e$ 行每行描述一条边，包含四个数字 $s1$, $s2$, $p$, $f$：

• $s1$ 和 $s2$（$0 \leq s1 < s2 < n$）表示通过该边相连的两个正方形的编号。 • $p$ 表示正方形 $s2$ 相对于 $s1$ 的位置。$p = 0, 1, 2, 3$ 分别表示 $s2$ 位于 $s1$ 的上方、左方、下方或右方（见示意图）。 • $f = 0, 1, 2$ 表示沿该边不折叠、向前折叠或向后折叠（见示意图）。

可以假设展开图是连通的，并且可以在平面上绘制而不重叠。

输入文件的最后一行是两个零（代替 $n$ 和 $e$），无需处理该行。

输出格式

对于每个测试用例，首先打印 "Test case #k:"，其中 $k$ 是测试用例的编号（从 1 开始）。

然后，在同一行打印： • 如果展开图不能形成闭合表面，则输出 "not a closed surface"。 • 如果可以形成闭合表面，则输出 "closed surface, volume=" 并跟随体积的整数值。

示例输入 1

6 5
0 2 2 1
1 2 3 1
2 3 3 1
2 4 2 1
4 5 2 1
5 4
0 2 2 1
1 2 3 1
2 3 3 1
2 4 2 1
0 0

示例输出 1

Test case #1: closed surface, volume=1
Test case #2: not a closed surface

提示

来源：2000年中欧地区编程竞赛