Simple Cactus Generator Language

NEERC has presented several cactus‐related problems over the years. A cactus is a connected undirected graph in which every edge belongs to at most one simple cycle – an obvious generalization of a tree where some cycles are allowed.

In this problem you are given a cactus described in the simplified cactus generator language (SCGL). The syntax of SCGL is defined by the following EBNF:

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

A production rule for a graph denotes a graph with two labeled vertices – the first and the last. Its semantics are as follows:

1. The basic building block c denotes a graph with two vertices and one edge between them.
2. The rule c(σ) connects a list of graphs (\sigma) into a chain by merging the last vertex of the first graph with the first vertex of the second, and so on.
3. The rule loop(σ) also connects a list of graphs into a chain but then merges the last vertex of the last graph with the first vertex of the first graph to form a cycle. ((\sigma) must contain more than one graph.)
4. The rule t(σ) connects the list of graphs by merging all their first vertices.

When a repetition is specified using a number, range or variable, it produces several copies of the given graph (or of c if no graph is provided) and then connects them as indicated.

Your task is to parse the given SCGL string, build the corresponding cactus and output it by listing the minimal set of edge-distinct paths that cover the whole graph. In the output a path is represented as a sequence of vertex labels (positive integers). In a chain, consecutive bridges should be merged into one path, and in a cycle, list the cycle vertices (starting and ending at the same vertex). It is guaranteed that the input SCGL specification is well-formed and describes a cactus.

inputFormat

The input consists of a single line containing a valid SCGL string describing the cactus graph.

outputFormat

Output the cactus as a set of paths covering all edges exactly once. The first line contains an integer (P) denoting the number of paths. Each of the following (P) lines contains a space-separated list of vertex labels representing one path. For chains, merge consecutive bridges into one path; for cycles, output the cycle with the starting vertex repeated at the end.

sample

c

1 2