랜선 기부

다솜이는 집에 남아 있는 많은 랜선 중 일부만 남겨 N개의 방에 있는 컴퓨터를 모두 서로 통신할 수 있게 하려고 합니다. 나머지 랜선은 기부할 수 있습니다.

각 방에는 컴퓨터가 하나씩 있습니다. 두 컴퓨터가 직접 랜선으로 연결되어 있거나, 다른 컴퓨터들을 거쳐 연결될 수 있으면 서로 통신할 수 있습니다.

입력으로 현재 가지고 있는 랜선 정보가 주어집니다. 0이 아닌 각 문자는 해당 위치의 두 컴퓨터를 잇는 랜선 하나를 뜻합니다. 같은 두 컴퓨터 사이에 여러 랜선이 있으면 필요한 랜선만 남기고 나머지는 기부할 수 있으며, 자기 자신으로 이어지는 랜선은 연결에 도움이 되지 않습니다.

모든 컴퓨터가 서로 통신할 수 있도록 만들면서 기부할 수 있는 랜선 길이의 최댓값을 구하세요.

첫째 줄에 컴퓨터의 개수 N이 주어집니다.

둘째 줄부터 N개의 줄에 걸쳐 랜선 정보가 주어집니다. i번째 줄의 j번째 문자가 0이면 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없다는 뜻입니다. 그 밖의 문자는 랜선의 길이를 뜻합니다.

소문자 a부터 z까지는 각각 길이 1부터 26을 나타내고, 대문자 A부터 Z까지는 각각 길이 27부터 52를 나타냅니다.

N은 50 이하의 자연수입니다.

다솜이가 기부할 수 있는 랜선 길이의 최댓값을 첫째 줄에 출력합니다.

모든 컴퓨터가 서로 통신할 수 있게 만들 수 없다면 -1을 출력합니다.