Ana şi Bogdan joacă din nou un joc interesant. Ana desenează pe o foaie de hârtie un arbore (graf neorientat conex şi aciclic) cu N vârfuri numerotate de la 1 la N. Apoi elimină vârfurile arborelui în modul următor: determină frunza (vârf cu gradul 1) cu numărul cel mai mic, o elimină din arbore şi scrie pe o altă foaie de hârtie numărul vârfului conectat direct cu frunza eliminată.
Procedeul de eliminare continuă până când în arbore rămâne un singur vârf, iar pe foaie s-a obţinut o listă cu N-1 vârfuri.
Bogdan primeşte foaia de hârtie cu lista vârfurilor scrise de Ana pe parcursul eliminării şi trebuie să reconstituie arborele.
Cerinţă
Dată fiind lista vârfurilor scrise de Ana, scrieţi un program care să reconstituie arborele.
Date de intrare
Fişierul de intrare lista.in conţine pe prima linie un număr natural N care reprezintă numărul de vârfuri din arbore. Pe cea de a doua linie sunt scrise N-1 numere naturale separate prin câte un spaţiu reprezentând lista vârfurilor scrise de Ana.
Date de ieşire
Fişierul de ieşire lista.out va conţine N-1 linii, fiecare linie conţinând o muchie specificată prin cele două extremităţi ale sale, separate prin spaţiu. Muchiile pot fi afişate în orice ordine.