Kada informatičar i netko tko to nije čuju riječ stablo, pomisle na dvije povezane, no vrlo različite stvari. Srećom, u ovom zadatku neće biti takvih nesporazuma jer su obje interpretacije ispravne. Nikola voli prirodu pa često odlazi na izlete šumom i šećući gleda stabla, divi se njihovoj veličini, razgranatosti, paradoksalno pravilnoj nasumičnosti… U ovo proljetno doba, razloga za dići pogled prema ovim veličanstvenim bićima ima još i više: stabla su prepuna boja te je upravo to zaintrigiralo Nikolu.

Tako je jednoga dana promatrao veliko stablo s N čvorova, pri čemu je u svakom čvoru Nikola vidio jednu boju. Je li se tamo nalazio neki cvijet, životinja, ili je Nikola jednostavno poludio, teško je reći. No, jedno je sigurno: Nikola je u to stablo gledao jako dugo te je u matricu veličine N × N za svaka dva čvora zapisao broj različitih boja na jedinstvenom jednostavnom putu između njih uključujući početni i završni čvor. No, diveći se svim tim bojama, potpuno je zaboravio kako je stablo izgledalo i kojih su boja bili pojedini čvorovi.

Nikola treba vašu pomoć: iz matrice koju je zapisao odredite jedno moguće stablo i boje pojedinih čvorova koje odgovaraju danoj matrici. Boje označite prirodnim brojevima iz skupa {1, 2, …, N}. Jamčimo da Nikola nije pogriješio, tj. primjeri su takvi da rješenje uvijek postoji.

ULAZNI PODATCI

U prvom je retku redni broj podzadatka (1, 2 ili 3) opisanog u idućem odjeljku Bodovanje. U drugom je retku prirodan broj N (1 ≤ N ≤ 3000), broj čvorova stabla, označenih brojevima od 1 do N. Idućih N redaka sadrži po N prirodnih brojeva, pri čemu j-ti broj u i-tom od ovih N redaka označava broj različitih boja na jedinstvenom putu od čvora i do čvora j.

IZLAZNI PODATCI

U prvi redak ispišite N prirodnih brojeva između 1 i N, međusobno odvojenih razmakom, boje čvorova redom od čvora 1 do čvora N. U idućih N - 1 redaka ispišite po dva prirodna broja A, B sa značenjem da u stablu postoji veza između čvorova A i B. Redoslijed veza i redoslijed čvorova unutar pojedine veze nije bitan.