Ministarstvo

시간 제한1초메모리 제한1024 MB

요약

N개 정점의 토너먼트가 주어질 때, 각 정점에서 한 가지 색의 간선만으로 도달할 수 없는 다른 정점이 존재하도록 간선을 최소 개수의 색으로 칠하는 문제다.

난이도: 어려움10점 중 8점
유형: 그래프, 수학, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1

입력

예상 출력

예제 2
입력
```
3
0 1 1
0 0 1
0 0 0
```
예상 출력
```
-1
```

예제 3

입력

예상 출력