Cactus Generator

A cactus is a connected undirected graph in which every edge belongs to at most one simple cycle. It is a tree that is allowed to contain some cycles.

Writing cactus test data with thousands of vertices by hand is tedious, so judges write it in SCGL, the Simple Cactus Generator Language, which describes a large cactus in a few characters. Parse an SCGL definition and print the cactus it describes.

An SCGL definition is the graph non-terminal of the grammar below, written in Extended Backus-Naur Form (EBNF).

   graph = "c"
         | "c(" list ")"
         | "loop(" list ")"
         | "t(" list ")"
    list = graph { "," graph }
         | ( number | range | variable ) [ "," graph ]
  number = nzdig { "0" | nzdig }
   nzdig = "1" | "2" | ... | "8" | "9"
   range = "range(" variable "," numvar "," numvar ")"
variable = "A" | "B" | ... | "Y" | "Z"
  numvar = number | variable

Each graph denotes a graph with two labeled vertices, its first vertex and its last vertex.

• c is the graph with two vertices, one first and one last, joined by a single edge.
• $\mathtt{c}(\sigma)$ links the graphs of the list $\sigma$ from left to right into a chain: the last vertex of the first graph is merged with the first vertex of the second graph, the last vertex of the second graph with the first vertex of the third graph, and so on. The first vertex of the result is the first vertex of the first graph of $\sigma$, and the last vertex of the result is the last vertex of the last graph of $\sigma$.
• $\mathtt{loop}(\sigma)$ links the graphs of $\sigma$ into a chain exactly as $\mathtt{c}(\sigma)$ does, and then also merges the last vertex of the last graph with the first vertex of the first graph. The first and the last vertices of the result are the first and the last vertices of the first graph of $\sigma$. A loop rule can be applied only to a list of more than one graph.
• $\mathtt{t}(\sigma)$ merges the first vertices of all graphs of $\sigma$ into one vertex. The first and the last vertices of the result are the first and the last vertices of the first graph of $\sigma$.

A list is written either as graphs separated by commas, or as a repetition. A repetition is a number, a range, or a variable, optionally followed by a comma and one graph. A repetition that names no graph repeats c.

A repetition written as a number denotes a list holding that many copies of the given graph. A repetition written as a variable denotes a list holding as many copies as the current value of that variable.

A repetition written as $\mathtt{range}(\nu, \alpha, \beta)$ carries a variable $\nu$ and two numbers $\alpha$ and $\beta$. If $\xi$ is a graph, then $\mathtt{c}(\mathtt{range}(\nu, \alpha, \beta), \xi)$, $\mathtt{loop}(\mathtt{range}(\nu, \alpha, \beta), \xi)$ and $\mathtt{t}(\mathtt{range}(\nu, \alpha, \beta), \xi)$ are range-enabled rules, and $\nu$ is a bound variable in $\xi$. Such a rule repeats $\xi$ exactly $|\beta - \alpha| + 1$ times. List the consecutive integers between $\alpha$ and $\beta$ inclusive in ascending order; in the $i$-th copy of $\xi$, every occurrence of $\nu$ is replaced by the $i$-th integer of that list. The $|\beta - \alpha| + 1$ graphs produced this way form a list, which is then linked by the rule that holds the repetition. $\alpha$ and $\beta$ may themselves be variables bound by an outer range-enabled rule.

In a well formed definition each letter from A to Z appears at most once as the $\nu$ of a range, and every other occurrence of a letter is bound.

If $\xi$ is a graph, then $\xi$, $\mathtt{c}(\xi)$, $\mathtt{c}(1, \xi)$, $\mathtt{t}(\xi)$ and $\mathtt{t}(1, \xi)$ all denote the same graph. $\mathtt{loop}(\xi)$ and $\mathtt{loop}(1, \xi)$ are not allowed.

One line holds a well formed cactus definition in SCGL. The syntax and the semantics of SCGL alone do not force the described graph to be a cactus, but the given definition always describes one: every edge belongs to at most one simple cycle, and no two vertices are joined by more than one edge. For example, neither loop(3,loop(3)) nor loop(2) ever appears in the input.

The line is at most 1000 characters long and describes a cactus with at most 50000 vertices. Every integer written as a number is at most 50000.

The vertex numbers are fixed by the construction, so exactly one answer is correct. Expand every repetition into its copies, then read the expanded definition from left to right. Each occurrence of the single edge graph c creates its first vertex and then its last vertex, and vertices take the numbers 1, 2, 3 and so on in the order they are created. When several vertices are merged into one, the merged vertex keeps the smallest of their numbers. After every merge is done, renumber the surviving vertices from 1 to $n$ keeping their order. Vertex 1 is then the first vertex of the whole graph.

Print three integers $n$, $m$ and $p$ on the first line. $n$ is the number of vertices, $m$ is the number of edges, and $p$ is the smallest number of paths that together traverse every edge exactly once. A single path may visit a vertex several times, but it never repeats an edge.

Print $m$ more lines, one per edge. Each of them holds the two endpoints $u$ and $v$ of one edge with $u < v$. Sort these lines by $u$, and by $v$ where $u$ is equal.