Company Restructuring
Time limit1sMemory limit128 MB
Given a rooted tree where reporting edges may only be rewired within original parent-child-sibling triples, output a new tree with at most 2 children per node and at most one higher-IQ child than its manager.
Problem
A software company has N employees. Every employee except the president has exactly one manager. The president has at least one direct report, and the reporting relation contains no cycle. In other words, the current company structure is a rooted tree.
The workgroup of employee E consists of E and E's direct reports. Employee E is the manager of that workgroup.
Each employee's intelligence quotient (IQ) is a natural number between 50 and 200, inclusive.
The president wants to rebuild the reporting structure to improve efficiency. The new structure must satisfy all of the following conditions.
- No workgroup may contain more than 3 members. Equivalently, each employee may have at most 2 direct reports.
- In each workgroup, at most 1 member may have a higher IQ than the manager.
- If employee E has manager M in the new structure, then M and E must have belonged to the same workgroup in the original structure.
The figure above shows one possible initial structure. Each node contains an employee number and that employee's IQ. This structure has two workgroups with 4 members, and some workgroups have at least two employees whose IQ is higher than their manager's, so it does not satisfy the conditions.
The structure can be changed as shown above so that all three conditions are satisfied.
Given the current company structure, output one new reporting structure that satisfies all conditions.
The input is guaranteed to have at least one answer. There may be several valid new structures; output any one of them.
Input
The first line contains the number of employees N. (2 <= N <= 1,000)
The second line contains the IQ of each employee in increasing order of employee number. Employees are numbered from 1 to N, and each IQ is a natural number between 50 and 200, inclusive.
Each of the next N-1 lines contains two natural numbers M and E. (1 <= M <= N, 1 <= E <= N) This means that M is the manager of E in the original structure.
Output
Output exactly N-1 lines.
Each line must contain two natural numbers M and E, meaning that M is the manager of E in the new structure.