시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB42266.667%

문제

Ivica je predsjednik države u nastajanju. Svaka takva država mora riješiti problem prometne povezanosti izgradnjom pripadajuće infrastrukture.

U državi ima N gradova. Ivica želi izgraditi N-1 dvosmjernu cestu između tih gradova tako da se može od bilo kojeg grada, koristeći samo te ceste, doputovati do bilo kojeg drugog grada.

Svaki gradonačelnik je javio Ivici rezultate referenduma o utjecaju na ekonomiju i zagađenje takvog projekta te inzistira da grad i mora imati točno Di cesta prema drugim gradovima.

Ivicu zanima je li moguće izgraditi N-1 dvosmjernu cestu tako da se zadovolje želje svih gradova.

입력

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100000), broj gradova iz teksta zadatka.

U drugom retku nalazi se N brojeva Di (0 ≤ Di ≤ N-1) odvojenih razmakom, brojevi iz teksta zadatka.

출력

U prvi redak treba ispisati NE ukoliko nije moguće ispuniti želje svih gradova ili DA u suprotnom.

U slučaju da je odgovor DA treba ispisati N-1 red, u svakom po par i<j koji označava cestu između gradova i i j tako da zadovoljavaju tražene uvjete. Redoslijed ispisa parova nije bitan.

예제 입력 1

1
1

예제 출력 1

NE

예제 입력 2

3
1 1 2

예제 출력 2

DA
1 3
2 3

예제 입력 3

5
3 2 1 1 1

예제 출력 3

DA
1 2
1 3
1 4
2 5