조직 구조 재편

직원이 N명인 소프트웨어 회사가 있다. 사장을 제외한 모든 직원은 정확히 한 명의 상사를 가진다. 사장에게는 직속 부하가 적어도 한 명 있으며, 상사 관계에는 사이클이 없다. 즉, 현재 회사의 상사 구조는 하나의 트리이다.

직원 E의 워크그룹은 E와 E의 직속 부하들로 이루어진다. 이때 E를 그 워크그룹의 상사라고 한다.

각 직원의 지능 지수(IQ)는 50 이상 200 이하의 자연수로 주어진다.

사장은 효율을 높이기 위해 상사 구조를 다시 만들려고 한다. 새 구조는 다음 조건을 모두 만족해야 한다.

1. 어떤 워크그룹도 구성원이 3명을 넘으면 안 된다. 즉, 한 직원의 직속 부하는 최대 2명이다.
2. 각 워크그룹에서 상사보다 IQ가 높은 구성원은 최대 1명이다.
3. 새 구조에서 어떤 직원 E의 상사가 M이라면, M과 E는 기존 구조의 어떤 워크그룹에 함께 속해 있어야 한다.

위 그림은 가능한 초기 구조의 한 예이다. 각 노드에는 직원 번호와 IQ가 적혀 있다. 이 구조에는 구성원이 4명인 워크그룹이 두 개 있으며, 일부 워크그룹에는 상사보다 IQ가 높은 직원이 2명 이상 있어 조건을 만족하지 못한다.

위 그림처럼 상사 구조를 바꾸면 세 조건을 모두 만족할 수 있다.

현재 회사의 상사 구조가 주어질 때, 조건을 모두 만족하는 새로운 상사 구조를 하나 출력하라.

입력은 항상 답이 존재하는 경우만 주어진다. 가능한 새 구조가 여러 개일 수 있으며, 그중 아무거나 출력해도 된다.

첫째 줄에 직원 수 N이 주어진다. (2 <= N <= 1,000)

둘째 줄에는 직원 번호가 증가하는 순서대로 각 직원의 IQ가 주어진다. 직원 번호는 1번부터 N번까지이며, 각 IQ는 50 이상 200 이하의 자연수이다.

다음 N-1개의 줄에는 두 자연수 M과 E가 주어진다. (1 <= M <= N, 1 <= E <= N) 이는 기존 구조에서 M이 E의 상사라는 뜻이다.

총 N-1개의 줄을 출력한다.

각 줄에는 두 자연수 M과 E를 출력한다. 이는 새 구조에서 M이 E의 상사라는 뜻이다.