TVRTKA

문제

A software company has N employees. Each employee, with the exception of the head of the company, has a manager. The head of the company is manager to at least one employee. There are no cycles in the management structure (an employee cannot be, directly or indirectly, superior to himself). In other words, there is a tree-like hierarchy in the company. 

A workgroup consists of an employee E and all employees he manages. We say that E is the manager of that workgroup. 

Each employee's intelligence quotient (IQ) is represented by an integer. 

The company’s management has decided to reorganize the hierarchy in order to improve efficiency. 

The new hierarchy must meet the following requirements: 

1. Each workgroup in the new hierarchy should have no more than 3 members. 
2. In each workgroup in the new hierarchy, no more than one member may have a higher IQ than the manager of the workgroup. 
3. Every employee and his (her) new manager must have belonged to the same workgroup in the old hierarchy. 

[이미지 1]

The initial hierarchy in the company. Each node in the tree shows the index of the employee and his (her) IQ. This hierarchy does not meet the above requirements since there are two workgroups with four members (requirement 1 is not met) and, furthermore, workgroups with managers 1 and 8 do not meet requirement 2. 

[이미지 2]

One possible hierarchy after reorganizing. All three requirements are met. 

Write a program that, given the description of the initial hierarchy, reorganizes the company so that the new hierarchy meets all of the above requirements. 

The input data will be such that a solution will always exist, although it will not necessarily be unique. 

입력

The first line of input contains an integer N (2 ≤ N ≤ 1 000), the number of employees in the company. 

The second line of input contains N integers separated by single spaces. Each number represents the intelligence quotient of one employee. Employees are numbered 1 to N in the order in which their IQs are given. All IQs are between 50 and 200, inclusive. 

Each of the following N−1 lines contains two integers M and E (1 ≤ M ≤ N, 1 ≤ E ≤ N), meaning that employee M is the manager of employee E in the initial hierarchy.

출력

Output should consist of exactly N-1 lines. 

Each line of output should contain two integers M and E separated by a space, meaning that the employee M is the manager of employee E in the new hierarchy. The new hierarchy should satisfy all the requirements from the task description.