omida

Definitie:

O "omida" este un arbore cu urmatoarea proprietate: exista un lant central astfel încât fiecare nod al arborelui fie apartine lantului central fie este adiacent lantului. Figurile de mai jos ilustreaza doua "omizi", nodurile gri indicând lantul.

"Omida" 1	"Omida" 2
Figura 1	Figura 2

Pot exista mai multe lanturi. De exemplu, un alt lant pentru "omida" 2 este 3-2-5-9.

Cerinte
Scrieti un program care, fiind data o "omida" cu N noduri, va eticheta nodurile cu numere de la 1 la N ce satisfac conditiile:

• fiecare eticheta de la 1 la N este folosita o singura data;
• nu vor exista doua muchii cu acelasi modul al diferentei dintre etichetele nodurilor adiacente.

Mai jos este ilustrat un mod de etichetare a "omidei" 2. Modulele diferentelor sunt indicate pe muchiile respective.

Figura 3

Date de intrare
Fisierul de intrare omida.in contine pe prima linie N, un numar întreg ce indica numarul de noduri. Fiecare dintre urmatoarele N-1 linii contine X Y doua numere întregi, separate printr-un spatiu, reprezentând doua noduri adiacente conectate cu o muchie.

Datele de intrare sunt corecte si arborele dat este o "omida."

Date de iesire
Fisierul de iesire omida.out contine o singura linie care contine L1 L2 ... LN (N numere întregi, separate prin cate un spatiu, unde Li reprezinta eticheta asociata nodului i).

În cazul când exista mai multe solutii, se va prezenta numai una. Daca nu este posibila nici o etichetare, fisierul de iesire va contine pe unica linie cuvântul IMPOSIBIL.

Restrictii
2 <=N <=10000

Exemplu
Fisierul de intrare (omida.in) descrie "omida" din Figura 2, iar fisierul de iesire (omida.out) descrie etichetarea din Figura 3.

omida.in
9
1 2
6 5
5 7
4 2
2 3
8 5
2 5
5 9

omida.out (o solutie posibila)
8 1 5 2 9 4 6 3 7

Timp maxim de executie/test: 0.1 secunde