Дрва су јако интересантна жива врста. Упркос томе шта су вам причали на часовима биологије, она заправо су само колекције \(N\) тачака и \(N-1\) дужи између парова њих, тако да крећући се само по паровима тачака спојених дужима је могуће стићи од сваке тачке до сваке друге.

Оно што вас исто нису научили на часовима биологије је да дрва имају јако развијен смисао за моду. Стабла се облаче тако што свакој њиховој тачки припише један позитиван цео број број (њихов еквивалент боја). Кроз историју различита бојења су била популарна почевши од традиционалних монохроматских до данашњих “ретро” црно-белих (оно што ми читамо као \(1\)-\(2\)).

Међутим, наш херој, Мирко, је једно јако креативно и неконвенцијално дрво. Стога, он жели да започне нови тренд у свету дрвене моде и да свакој тачки додели неки број, тако да ако је некој тачки доделио број \(x\), онда је та тачка дужима повезана са тачно \(x\) тачака којима није доделио \(x\) (и могуће још некима којима јесте доделио \(x\)). Мирко је сасвим сигуран да ће променити свет дрвене моде заувек, ако успе да дизајнира своје одело. Да би то урадио потребна му је ваша помоћ.

Описи функција

Потребно је да имплементирате функцију

• \(Oboji(N, U[\ldots], V[\ldots], C[\ldots])\)

где је \(N\) број који представља број тачака који има Мирко, низови \(U\) и \(V\), дужине \(N-1\) представљају да постоји дуж између тачака \(U[i]\) и \(V[i]\). У низ \(C\) дужине \(N\) треба да упишете вредности бројева које Мирко треба да додели тачкама, или да цео низ буде једнак \(-1\) уколико то није могуће. Сви низови су индексирани од 1. ## Пример

Нека је \(N=4\), и нека су низови \(U=\{1,1,1\}\) и \(V=\{2,3,4\}\): Тада је могуће изабрати \(C=\{3,1,1,1\}\), јер је тада тачка \(1\) боје \(3\) спојена са три тачке боје \(1\), што оправдава његову боју, док су сви остали боје \(1\) и спојени су само са једном тачком, која је при томе различите боје.

Нека је \(N=4\), и нека су низови \(U=\{1,2,3\}\) и \(V=\{2,3,4\}\): Тада решење не постоји и треба изабрати \(C=\{-1,-1,-1,-1\}\).

Ограничења

• \(1 \leq N \leq 300.000\)
• \(1 \leq U_i,V_i \leq N\)
• Гарантује се да је дрво ## Подзадаци Тест примери су подељени у \(6\) подзадатка:
• [6 поена]: Свака тачка је повезана са највише две друге тачке.
• [9 поена]: \(N\leq20\)
• [24 поена]: \(N\leq500\)
• [16 поена]: \(N\leq3000\)
• [12 поена]: Свака тачка је повезана са највише \(10\) других тачака.
• [33 поена]: Нема додатних ограничења ## Детаљи имплементације

Потребно је да пошаљете тачно један фајл sasavo_odelo.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void Oboji(int N, int* U, int* V, int* C);

Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду број \(N\).
• У наредних \(N\) редова по \(2\) броја. У \(i\)-том реду налазе се бројеви \(U_i, V_i\).

Затим овај програм зове вашу функцију и штампа \(N\) бројева које представљају бојење које врати функција.