描述

可扩展标记语言（$XML$，$eXtensible Markup Language$）在可预见的未来有望成为结构化数据通信的通用语言，部分原因在于其严格的格式要求。$XML$ 解析器必须报告任何违反格式良好的 $XML$ 文档规则的情况。如果一个 $XML$ 文档满足万维网联盟（$W3C$）$XML$ 规范所定义的所有格式良好性约束，那么就称该 $XML$ 文档是格式良好的。

$XML$ 文档由称为元素的单元组成，这些元素包含字符数据和/或其他元素。

元素在其声明中也可能包含称为属性的值。考虑以下 $XML$ 文档：

   <name>

           <first>John</first>

           <last>Doe</last>

   </name>

   <address>

           <street>

                   <number>15</number>

                   <direction>West</direction>

                   <name>34th</name>

           </street>

           <city>New York</city>

           <state-code>NY</state-code>

           <zip-code format="PLUS4">10001-0001</zip-code>

           <country-code>USA</country-code>

   </address>

   <orders/>

尖括号内加粗的标识符是文档的元素。“zip-code” 元素内斜体的标识符 “format” 是该元素的一个属性。除了 “orders” 之外，所有元素都有开始声明和结束声明，也称为标签。“orders” 元素是一个空元素，由关闭该元素的 “/>” 序列表示，不需要单独的结束标签。第一行是针对 $XML$ 解析器的处理指令，不被视为文档的元素。

格式良好的文档的规则如下：

1. 恰好有一个元素不包含在任何其他元素内。这个元素被标识为 “根” 或 “文档” 元素。在上面的示例中，“customer” 是文档元素。

2. $XML$ 文档的结构必须正确嵌套。如果一个元素是非空元素，那么它的开始标签必须与结束标签配对。

3. 元素结束标签中的名称必须与开始标签中的元素类型匹配。例如，用

   打开的元素必须用
   关闭。

4. 任何属性在同一个开始标签或空元素标签中不能出现多次。

5. 已解析的元素不能包含对自身的递归引用。例如，在一个 address 元素内再包含另一个 address 元素是不合适的。

6. 一个命名属性必须有一个关联的值。

输入

输入将包含一系列 $XML$ 文档。每个文档的开始由仅包含处理指令 “” 的一行来标识。输入的结束由仅包含文本 “” 的一行来标识（这不是真正的 $XML$ 处理指令，只是用于标记此问题输入结束的一个标记）。与所有 $XML$ 文档一样，元素和属性之间的空白应该被忽略。关于输入，你可以做以下假设：

唯一会出现的处理指令是 $XML$ 版本处理指令，并且它总是只出现在输入中每个文档的开头。

元素和属性名称区分大小写。例如，

<?xml version="1.0"?>
<acm-contest-problem>
        <title>A Well-Formed Problem</title>
        <text>XML, eXtensible Markup Language, is poised to become the lingua franca of
structured data communication for the foreseeable future. [...]</text>
        <input>probleme.in</input>
        <output>probleme.out</output>
</acm-contest-problem>
<?xml version="1.0"?>
<shopping-list>
        <items>
                <item quantity="1" quantity="1">Gallon of milk</item>
                <item>Frozen pizza
        </items>
</Shopping-list>
<errand-list>
        <errand>Get some cash at the ATM
                <errand>Pick up dry cleaning</errand>
        </errand>
</errand-list>
<?end?>

well-formed
non well-formed