Ministarstvo

문제

Pero se nakon uspješne karijere u stranci koju nećemo imenovati, zaposlio u Ministarstvu turizma. Pero nadgleda mrežu od $NN$ gradova, označenih brojevima od $11$ do $NN$, 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 $KK$ različitih dozvola, označenih od $11$ do $KK$, 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 $vv$ postoji neki grad $uu$, tako da iz grada $vv$ nije moguće doći do grada $uu$ posjedovanjem samo jedne dozvole.

Pero vas moli da mu pomognete, te da odredite najmanji $KK$ 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 $NN$.

U $ii$-tom od sljedećih $NN$ redaka nalazi se $NN$ brojeva $a_{i,j}a\_\{i,j\}$ gdje je $a_{i,j}=1a\_\{i,j\}\; =\; 1$ ako postoji cesta iz grada $ii$ u grad $jj$. Primijetite da je $a_{i,i}=0a\_\{i,i\}\; =\; 0$ te da je za $i\mathrm{\ne }ji\; \backslash ne\; j$ točno jedan od brojeva $a_{i,j}a\_\{i,j\}$ te $a_{j,i}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 $KK$.

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

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

힌트

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 $11$ nije moguće doći do grada $33$ koristeći samo jednu dozvolu.

Iz grada $22$ nije moguće doći do grada $11$ koristeći samo jednu dozvolu.

Iz grada $33$ nije moguće doći do grada $22$ koristeći samo jednu dozvolu.

Iz grada $44$ nije moguće doći do grada $11$ koristeći samo jednu dozvolu.

[이미지 1]