G11183 - FOLLOWING Grado 11

Order is an important concept in mathematics and in computer science. For example, Zorn’s Lemma states: “a partially ordered set in which every chain has an upper bound contains a maximal element.” Order is also important in reasoning about the fix-point semantics of programs. This problem involves neither Zorn’s Lemma nor fix-point semantics, but does involve order. Given a list of variable constraints of the form x < y, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the constraints x < y and x < z there are two orderings of the variables x, y, and z that are consistent with these constraints: xyz and xzy.

Input

 

The input consists of a sequence of constraint specifications. A specification consists of two lines: a list
of variables on one line followed by a list of constraints on the next line. A constraint is given by a pair
of variables, where ‘x y’ indicates that x < y.
All variables are single character, lower-case letters. There will be at least two variables, and no
more than 20 variables in a specification. There will be at least one constraint, and no more than 50
constraints in a specification. There will be at least one, and no more than 300 orderings consistent
with the constraints in a specification.
Input is terminated by end-of-file.

The input consists of a sequence of constraint specifications. A specification consists of two lines: a list of variables on one line, followed by a list of constraints on the next line.

A constraint is given by a pair of variables, where ‘x y’ indicates that x < y.

All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the constraints in a specification.

Input is terminated by end-of-file.

 

Output

The output should consist of the final state of the blocks world. Each original block position numbered i (0 ≤ i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don’t put any trailing spaces on a line. There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).

Example

Input:
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit


Output:
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:


Added by:MaratónAFDM
Date:2018-09-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C NCSHARP CSHARP C++ 4.3.2 JAVA JULIA PYTHON PYPY3 PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.