시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 0 0 0.000%

문제

직원이 N명인 소프트웨어 회사가 있다. 사장을 제외한 모든 직원은 상사를 가지고 있다. 사장의 직속 부하는 적어도 한 명이다. 또, 상사 구조가 사이클을 이루는 경우는 없다. 즉, 이 회사의 상사 구조는 트리와 같은 모양이다.

직원 E의 워크그룹이란 E와 그가 상사인 모든 직원으로 이루어져 있다. 이 때, E를 그 워크그룹의 상사라고 한다.

각 직원의 지능 지수(IQ)는 자연수로 나타낼 수 있다.

이 회사의 사장은 효율성을 증가시키기 위해서 상사 구조를 변화시키려고 한다. 새로운 구조는 아래와 같은 세 가지 조건을 만족해야 한다.

1. 워크그룹의 멤버의 수는 3명을 넘으면 안된다.

2. 각 워크그룹의 상사보다 높은 지능 지수를 가진 멤버의 수는 한 명을 넘을 수 없다.

3. 각 직원과 새 상사는 이전 구조에서 같은 워크그룹에 속해있는 사람이어야 한다.

위의 그림은 이 회사의 초기 구조이다. 트리의 각 노드에는 직원 번호와 그 직원의 IQ가 적혀져 있다. 이 구조에는 멤버의 수가 4인 워크그룹이 두 개나 존재하기 때문에, 문제의 조건을 만족시키지 않는다. 또, 직원 1과 8의 워크그룹은 조건 2를 위반한다.

따라서 위의 그림과 같이 구조를 바꿀 수 있다. 위의 구조는 세 가지 조건을 모두 만족시키는 구조의 예이다.

회사의 현재 구조가 주어졌을 때, 문제의 조건을 만족시키는 새로운 구조를 만드는 프로그램을 작성하시오.

항상 답이 존재하는 경우만 입력으로 주어진다. 하지만, 새로운 구조의 수가 여러가지일 수도 있다.

입력

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

둘째 줄에는 각 직원의 지능지수가 직원 번호가 증가하는 순서대로 주어진다. 직원 번호는 1번부터 N번까지이며, IQ는 50보다 크거나 같고, 200보다 작거나 같은 자연수이다.

다음 N-1개의 줄에는 두 자연수 M과 E가 주어진다. (1 ≤ M ≤ N, 1 ≤ E ≤ N) 이 뜻은 원래 구조에서 M이 E의 상사라는 의미이다. 

출력

출력은 총 N-1줄이다.

각 줄에는 M과 E를 출력하며, 새 구조에서 M이 E의 상사라는 의미이다. 

예제 입력

9
120 170 170 150 160 160 140 150 150
3 1
3 7
3 8
1 9
1 4
8 2
8 5
8 6

예제 출력

8 5
8 7
5 2
5 6
7 3
7 1
1 9
9 4

힌트