Problem Description

NEERC features a number of problems about cactuses – connected undirected graphs where every edge belongs to at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed.

In 2005, the first problem about cactuses appeared, simply called "Cactus". In 2007, it was "Cactus Reloaded", in 2010, "Cactus Revolution", and in 2013, "Cactus Automorphisms". Here is an example of a cactus used in those problems:

For four years, judges had to generate test files for cactuses with thousands of vertices. Naturally, a number of test generators of increasing complexity were built, culminating in a domain-specific language called CGL (Cactus Generator Language). CGL can compactly define a large cactus for testing purposes. In this problem, you need to parse a simplified version of this language, which we call SCGL (Simple Cactus Generator Language), and output the resulting cactus.

A cactus must be output by listing the minimal set of edge-distinct paths that cover the entire graph.

The syntax of SCGL cactus definition is represented by the graph non-terminal in the grammar given below using the 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

A graph production rule denotes a graph with two labeled vertices – the first and the last. Graph definition rules have the following semantics:

• The basic building block c denotes a graph with just two vertices (one is the first and the other is the last) and one edge.
• The c(σ) rule connects a specified list of graphs σ from left to right, merging the last vertex of the i-th graph with the first vertex of the (i+1)-th graph. The resulting graph's first vertex is the first vertex of the first graph in the list, and the last vertex is the last vertex of the last graph in the list.
• The loop(σ) rule is similar to c(σ), but the last vertex of the last graph is merged with the first vertex of the first graph, forming a loop. The resulting graph's first and last vertices are the first and last vertices of the first graph in the list. A loop can only be applied to lists with more than one graph.
• The t(σ) rule connects a specified list of graphs σ, merging their first vertices. The resulting graph's first and last vertices are the first and last vertices of the first graph in the list.

The list of graphs is either specified explicitly by a comma-separated list or using a list repetition with a number, range, or variable, optionally followed by a comma and a graph. When a graph is not explicitly specified in a list repetition, the given graph is assumed to be c.

The simplest list repetition is defined using a number non-terminal. It denotes a list of graphs with the specified integer number of copies of the given graph.

A range list repetition is defined by the range(ν, α, β) rule, which has three components – a variable ν, and numbers α and β. If ξ is a graph, then c|loop|t(range(ν, α, β), ξ) are called range-enabled rules, and the variable ν is called a bound variable in ξ. In the context of a range-enabled rule, ξ is repeated |β − α| + 1 times to form a list. Each occurrence of variable ν in ξ is replaced by consecutive integers between α and β inclusive in ascending order. This produces a list of |β − α| + 1 graphs, which are then connected according to the specification of the corresponding range-enabled rule. α and β themselves might refer to variables bound in the outer range-enabled rule.

In a well-formed graph:

• Each variable non-terminal (a letter from A to Z) occurs at most once as ν in range(ν, α, β) rules.
• All other occurrences of variable non-terminals allowed by the grammar are bound.

Note that if a character sequence ξ is a graph, then ξ, c(ξ), c(1, ξ), t(ξ), and t(1, ξ) all denote the same graph. On the other hand, neither loop(ξ) nor loop(1, ξ) are allowed.

The following examples illustrate these basic rules. The graphs have their first and last vertices marked with letters F and L, respectively.

Input Format

The input file contains a single line with a well-formed cactus definition in SCGL. While the syntax and semantics of SCGL themselves do not guarantee that the resulting graph is a cactus, the input file for this problem always defines a cactus – every edge belongs to at most one simple cycle and there are no multiple edges between vertices. For example, neither loop(3, loop(3)) nor loop(2) are possible.

The line in the input file is at most 1000 characters long and defines a cactus with at most 50,000 vertices. Integer numbers represented by number non-terminals do not exceed 50,000.

Output Format

The first line of the output file must contain two integer numbers n and m. Here n is the number of vertices in the graph. Vertices are numbered from 1 to n, where 1 is the number of the first vertex of the graph and n is the number of the last vertex of the graph. The other vertices can be numbered arbitrarily. Edges of the graph are represented by a set of edge-distinct paths, where m is the minimal number of such paths.

Each of the following m lines must contain a path in the graph. A path starts with an integer number k_i (k_i ≥ 2) followed by k_i integers from 1 to n. These k_i integers represent vertices of a path. A path can go through the same vertex multiple times, but every edge must be traversed exactly once in the whole output file.

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

c

Output Sample #2

2 1
2 1 2

Input Sample #3

c(2)

Output Sample #3

3 1
3 1 2 3

Input Sample #4

c(3)

Output Sample #4

4 1
4 1 2 3 4

Input Sample #5

t(c(3),c,c)

Output Sample #5

6 2
2 1 2
5 3 1 4 5 6

Input Sample #6

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

Output Sample #6

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

Notes

Time limit: 1 second, Memory limit: 256 MB.

见题面 Input 部分

见题面 Output 部分