31983번 - Ministarstvo 서브태스크점수다국어

Pero se nakon uspješne karijere u stranci koju nećemo imenovati, zaposlio u Ministarstvu turizma. Pero nadgleda mrežu od $N$ gradova, označenih brojevima od $1$ do $N$, gdje između svaka dva grada postoji točno jedna jednosmjerna cesta. Kako bi povećao prihode, odlučio je uvesti dozvole za prometovanje. Pero bi najradije uveo posebnu dozvolu za svaku cestu, no to bi alarmiralo njegove nadređene. Stoga, uvest će $K$ različitih dozvola, označenih od $1$ do $K$, te će za prolazak svakom cestom biti potrebno posjedovanje točno određene dozvole.

Kako bi ipak osigurao pozamašne prihode, Pero će se zadovoljiti sa sljedećim svojstvom.

• Za svaki grad $v$ postoji neki grad $u$, tako da iz grada $v$ nije moguće doći do grada $u$ posjedovanjem samo jedne dozvole.

Pero vas moli da mu pomognete, te da odredite najmanji $K$ takav da postoji pridruživanje dozvola s traženim svojstvom te neko takvo pridruživanje! Ako ne postoji takvo pridruživanje, ispišite -1.

U prvom je retku prirodan broj $N$.

U $i$-tom od sljedećih $N$ redaka nalazi se $N$ brojeva $a_{i,j}$ gdje je $a_{i,j} = 1$ ako postoji cesta iz grada $i$ u grad $j$. Primijetite da je $a_{i,i} = 0$ te da je za $i \ne j$ točno jedan od brojeva $a_{i,j}$ te $a_{j,i}$ različit od nula.

Ako ne postoji pridruživanje s traženim svojstvom u prvi i jedini redak ispište -1.

Inače, u prvi redak ispišite minimalan prirodan broj $K$.

U sljedećih $N$ redaka ispište opis pridruživanja.

U $i$-tom retku ispišite $N$ brojeva $b_{i,j}$ gdje ako je $a_{i,j} = 0$ tada je i $b_{i,j} = 0$, a u suprotnom $1 ≤ b_{i,j} ≤ K$ označava koja je dozvola potrebna za prometovanje tom cestom.

U svim podzadacima vrijedi $2 ≤ N ≤ 1000$. U svakom podzadatku, $15\%$ bodova donosi samo odlučivanje je li takvo pridruživanje postoji ili ne. Za te bodove potrebno je, ako niste ispisali -1, ispisati nekakvo pridruživanje, ali ono ne mora zadovoljavati Perino traženo svojstvo.

Pojašnjenje trećeg probnog primjera:

Ceste za koje je potrebna prva dozvola su označene crvenom bojom, druga dozvola plavom i treća dozvola zelenom.

Iz grada $1$ nije moguće doći do grada $3$ koristeći samo jednu dozvolu.

Iz grada $2$ nije moguće doći do grada $1$ koristeći samo jednu dozvolu.

Iz grada $3$ nije moguće doći do grada $2$ koristeći samo jednu dozvolu.

Iz grada $4$ nije moguće doći do grada $1$ koristeći samo jednu dozvolu.