Description

NEERC 以大量关于仙人掌的题目为特色——每条边属于至多一个简单环连通的无向图。直观的说，仙人掌是一种一些环被允许的广义树。

2005年，第一个有关仙人掌的问题出现，这个问题被简单的叫做“仙人掌”。在2007年是“仙人掌再来”，在2010年叫做“仙人掌变革”，以及2013年是“仙人掌自同构”。以下是这些问题中使用的仙人掌例子：

四年来评测必须为顶点以千数的仙人掌生成测试文件。当然，复杂性日益增加的大量数据发生器被建立，最终有一个被称为 CGL（Cactus Generator Language，仙人掌发生器语言）的领域特定语言。CGL 可以为测试的目的简洁地定义一个大仙人掌。本题中你要解析该语言的我们称为 SCGL（Simple Cactus Generator Language，简单仙人掌发生器语言）的一个简化版本，输出一个仙人掌作结果。

一个仙人掌要以列出边的极小集（覆盖全图的不同路径）输出。

SCGL 仙人掌定义的语法由语法中的指定的用下面的扩展巴科斯-诺尔范式的非终止图表示：

$$\begin{aligned} graph &= “\texttt{\textup{c}}”&&&&&&&&&&&&&&&&&&&&&&&&&&&\\ &| “\texttt{\textup{c(}}” list “\texttt{\textup{)}}”\\ &| “\texttt{\textup{loop(}}” list “\texttt{\textup{)}}”\\ &| “\texttt{\textup{t(}}” list “\texttt{\textup{)}}”\\ \end{aligned}$$$$\begin{aligned} list &= graph \{ “\texttt{\textup{,}}” graph \}&&&&&&&&&&&&\\ &|(number | range | variable ) [ “\texttt{\textup{,}}” graph ]\\ \end{aligned}$$$$\begin{aligned} &number = nzdig \{ “\texttt{\textup{0}}” | nzdig \}\\ &nzdig = “\texttt{\textup{1}}” | “\texttt{\textup{2}}” | \cdots | “\texttt{\textup{8}}” | “\texttt{\textup{9}}”\\ &range = “\texttt{\textup{range(}}” variable “\texttt{\textup{,}}” numvar “\texttt{\textup{,}}” numvar “\texttt{\textup{)}}”\\ &variable = “\texttt{\textup{A}}” | “\texttt{\textup{B}}” | \cdots | “\texttt{\textup{Y}}” | “\texttt{\textup{Z}}”\\ &numvar = number | variable \end{aligned}$$

一个图的制造规则表示一个有两个点标记的图——首和尾。图定义规则有以下语义：

• 基本建立块 $c$ 列表示一个仅有两个点（一首一尾）标记与一边的图。

• $c(σ)$ 规则对于含有 $n$ 个图的指定图列表 $σ$ 将第 $i$ 图尾顶点与第 $i+1$ 图首顶点合并，加入列表。（$i\in\mathbb{N}^*,1\le i< n$）结果图的首顶点为第一图首顶点，尾顶点为第 $n$ 图尾顶点。

• $loop(σ)$ 规则与 $c(σ)$相似，但第 $n$ 图尾顶点与第一图首顶点合并,加入列表。结果图的首尾顶点为列表中第一图首尾顶点。环仅可被应用于一图以上的列表。

• $t(σ)$ 规则连接一个指定图列表 $σ$，合并他们的首顶点。结果图的首尾顶点为列表中第一图首尾顶点。

图列表不是以一逗号分隔列表明确指定，就是用一个有一个数字、范围或变量的选择性地跟随一个逗号或图的可重列表指定。当一图非于一可重列表中明确指定，则该指定图被假定为 $c$。

最简单的可重列表用一个非终止数定义。它表示一个有指定整数个指定图的副本的列表。

一个可重范围列表由有三个组件（变量 $ν$，数字 $α$ 与 $β$）的 $range(ν, α, β)$ 规则定义。若 $ξ$ 字符序列为一图，则 $c|loop|t(range(ν, α, β), ξ)$ 被称为范围启用规则，变量 $ν$ 被称为 $ξ$ 中的一个约束变量。在一个范围启用规则的语境中，$ξ$ 被重复 $|β − α| + 1$ 次以建立列表。变量 $ν$ 于 $ξ$ 中的每次出现按升序由连续的 $α$ 与 $β$ 之间的整数（包括 $α$ 与 $β$）取代。 那产出一个包括 $|β −α|+ 1$ 个图的列表，通过相应的范围启用规则的规范连接。$α$ 与 $β$ 自身可能指被约束于外范围启用规则的变量。

在一个语法正确的图中：

• 每一个非终止变量（一个从 A 到 Z 的字母）作为 $range(ν, α, β)$ 规则中的 $ν$ 至多存在一次；

• 非终止变量的语法允许的所有其他事件被绑定。

注意，若一字符序列 $ξ$ 为一图，那么 $ξ, c(ξ), c(1 , ξ), t(ξ),$ 与 $t(1 , ξ)$ 都指此一图。另一方面，不论 $loop(ξ)$ 还是 $loop(1 , ξ)$ 都不被允许。

下列例子说明这些基本规则。这些图有以 F 与 L 相应标记的始末点。

Input Format

输入文件包含一行，含有一个 SCGL 定义。定义格式正确，总描述一仙人掌，每条边属于至多一个简单环，无重边。比如，$loop(3 , loop(3))$ 与 $loop(2)$ 都不可能。

输入文件中该行至多长 $1000$ 字符，定义的仙人掌至多 $50000$ 个顶点。由非终止数代列表的整数不超过 $50000$。

Output Format

输出文件第一行必须包含两个整数 $n$ 与 $m$。$n$ 为图顶点数。顶点由 $1$ 到 $n$ 编号，$1$ 为首点编号，$n$ 为图尾点编号。其他点可随意编号。图中边由一个边不重路径集代表，$m$为该集合最小路径数。

后 $m$ 行，每行必须包含图中一条路径。一条路径以一个整数 $k_{i} (k_{i} \ge 2)$ 开始，后随 $k_{i}$ 个整数从 $1$ 到 $n$。这 $k_{i}$ 个整数代列表一条路径的顶点。一条路径可经过同一顶点多次，但每条边必须在整个输出文件中刚好经过一次。

注释

此题中出现的的EBNF：

非终端符号为被定义的语言的句法部分。

终端符号为由一个或多个字符组成的序列，是构成语言的不可约元素。

本题中一条语法规则形如$元标识符=定义列表$

定义列表形如$主要句法|主要句法|\cdots$。

其中主要句法为可选序列、重复序列、分组序列、元标识符、终端字符串、空序列之一。

可选序列形如[定义列表]，重复序列形如{定义列表}，分组序列形如(定义列表)。

元标识符是以字母开头的字母数字序列，即非终端符号的名称。

由语法定义的语言的终端符号由终端字符串表示，终端字符串形如“一个或多个除该引号符号以外的任何终端字符的序列” 。

EBNF的终端符号称为终端字符，是字母、数字, 与=|{}“()[]字符之一。

需要注意的是，这里给出的EBNF不完整，但足以解决题目。

c(c,t(loop(3),c(c,loop(6))),loop(c,c,t(c,loop(4))))

15 1
19 1 2 9 10 11 12 13 10 15 9 14 2 3 4 5 6 7 8 3

c

2 1
2 1 2

c(2)

3 1
3 1 2 3

c(3)

4 1
4 1 2 3 4

t(c(3),c,c)

6 2
2 1 2
5 3 1 4 5 6

c(2,t(c(2),c,c))

9 3
3 2 1 3
3 4 5 6
5 1 7 5 8 9