Problem H. Hierarchy Model ≡

Statement

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:

• Non-commutative: The order of operands matters.
• Commutative: The order of operands does not matter.

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.

Input format

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 format

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.

Constraints

Operation codes and base object indices are integers between 0 and 2³² − 1.

The total number of nodes does not exceed 2 ⋅ 10⁵.

Sample tests

123 2
103 3
1 0
2 0
3 0
103 3
3 0
2 0
1 0

6 4
7 3
8 2

122 2
102 3
1 0
2 0
3 0
102 3
3 0
2 0
1 0

5 1