Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 256 Mb | |
Output file: | Standard output |
In a CAD system, models are represented as trees. Leaf nodes reference basic objects, and intermediate nodes represent operations performed on them.
All base objects are unique. Each operation produces a new object. Objects generated by the same set of operations are considered identical.
Operations are of two types:
The goal is to compress the tree by replacing some of its subtrees with references to equivalent objects, minimizing the total number of remaining nodes.
The input specifies the tree in the following format:
The root node contains an operation code (odd for non-commutative, even for commutative).
The number of its children (possibly zero). The subsequent lines describe all its children recursively in the same format.
Leaf nodes specify the index of a base object instead of an operation code.
Output pairs of values:
The index of the original node and the index of the node it should be replaced with.
The numbering of nodes starts from zero and corresponds to the order of their appearance in the input file.
If compression cannot be performed, the output should be empty.
Operation codes and base object indices are integers between 0 and 232−1.
The total number of nodes does not exceed 2⋅105.
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|