Malha Aérea

No reino de Quadradônia, o monarca quer rever todas as tarifas aéreas. Para isso, pediu ao seu contador uma tabela com as propostas de novos preços.

Todavia, o monarca estudou no Instituto de Computação e Programação de Chapecó (ICPC) e tem conhecimento suficiente para exigir coerência na tabela. A tabela é coerente se nenhuma rota com escalas é mais barata do que o voo direto.

Verificada a coerência da tabela, o monarca gostaria de diminuir o número de voos diretos, sem contudo aumentar os custos das viagens.

Seu problema é verificar a coerência da tabela e, sendo esta coerente, informar ao monarca quantas voos diretos podem ser eliminados sem encarecer o custo de qualquer viagem.

A primeira linha contém $N$ $(1 ≤ N ≤ 100)$, que é o número de cidades da Quadradônia servidas por voos. Existem então mais $N$ linhas, $L_1 , L_2 , ... , L_N$ . A linha $L_i$ contém $N$ inteiros, $C_{i1} , C_{i2} , ... , C_{iN}$, onde $C_{ij}$ é o custo do voo direto entre as cidades $i$ e $j$. O custo de ida e de volta entre duas cidades é sempre igual, ou seja, $C_{ij} = C_{ji}$ , para todos os pares ${i, j}$ tais que $1 ≤ i ≤ N e 1 ≤ j ≤ N$ . Quando $i = j, C_{ij} = 0$. Quando $i \ne j, 1 ≤ C_{ij} ≤ 10^3$ .

Imprima uma linha contendo um inteiro. Se a tabela for incoerente, o inteiro deve ser igual a -1. Se a tabela for coerente, o inteiro deve ser igual ao maior número de voos diretos que podem ser removidos sem aumento nos custos das viagens para os passageiros.