Read problems statements in Mandarin Chinese  and Russian. 

Codechef has now decided to make an admin panel amongst their chefs. This way they think that it would be easier for them to control and regulate their contests. To do so, they have asked them to rate everyone including themselves by a non-negative integer.

There are N chefs, numbered from 1 to N. Each chef has submitted a rating to the Codechef panel for other all the chefs including a rating to himself. Surprisingly for the team, for each pair of chefs (say, chef with the number i and the chef with the number j), they collaborated within themselves and gave the same rating to each other i.e. the rating that the chef i has given to the chef j is equal to the rating that the chef j has given to the chef i. The Codechef team built a rating matrix from this input from Chefs. Now, from this input rating matrix M, they will make a Paired rating matrix P as follows:

P is symmetric.
P_{i, j} is either equal to zero, or to M_{i, j}, where M_{i, j} is the rating given by i^{th} chef to the j^{th} chef.
There exists S > 0, such that each entry in P + P^{2} + ... + P^{S} is positive.
To make things more friendly between the admin panel of Chefs, the sum of values in P is minimum possible.

Help the Codechef panel in selecting such a matrix P from M. Please find the minimum possible sum of entries in the matrix P such that P will still satisfy the constraints.

------ Input ------ 

The first line of the input contains T, number of test cases to follow. Then T test cases follow.

Each test case start with a line containing an integer N, the number of chefs in Codechef team. 

Then N lines follow. Each of them contains N space-separated integers. The j^{th} integer in the i^{th} line is the rating given by chef with the number i to chef with the number j.

------ Output ------ 

For each test case, print the minimum sum of entries, possible for P. If it is not possible to do, print "-1" (without quotes).

------ Constraints ------ 

1 ≤ T ≤ 100
Constraints on N:
Subproblem 1 (30 points):  1 ≤ N ≤ 5
Subproblem 2 (70 points): 1 ≤ N ≤ 100

0 ≤ M_{i, j} ≤ 10^{9}

----- Sample Input 1 ------ 
2

2

1 0

0 1

2

1 1

1 1
----- Sample Output 1 ------ 
-1

2

Difficulty: VERY_HARD
Tags: Graph algorithms

Spanning trees

Sorting

Tree algorithms

Mathematics

Matrices

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
import sys

class Solver:

	def __init__(self, num_chefs):
		self.num_chefs = num_chefs
		self.ratings = [[0 for x in range(num_chefs)] for y in range(num_chefs)]
		self.mst = [[0 for x in range(num_chefs)] for y in range(num_chefs)]
		self.visited_nodes = [0 for x in range(num_chefs)]
		self.answer = -1

	def read_ratings(self):
		for num in range(self.num_chefs):
			self.ratings[num] = list(map(int, input().split()))

	def check_ratings(self):
		chef_a = 0
		for chefRating in self.ratings:
			if len(chefRating) != self.num_chefs:
				raise ValueError(f'Chef {chef_a} has not given rating to all chefs')
			for chef_b in range(len(chefRating)):
				if self.ratings[chef_a][chef_b] != self.ratings[chef_b][chef_a]:
					raise ValueError(f'Chef ratings is not symmetric {chef_a} {chef_b}')
				if self.ratings[chef_a][chef_b] < 0:
					raise ValueError(f'Chef rating is not a non-negative integer {chef_a} {chef_b}')
			chef_a += 1

	def solve(self):
		self.answer = -1
		if self.num_chefs == 1:
			if self.ratings[0][0] != 0:
				self.answer = self.ratings[0][0]
			return
		self.find_minimum_spanning_tree()
		if sum(self.visited_nodes) == len(self.visited_nodes):
			self.answer = self.get_sum_of_mst()

	def find_minimum_spanning_tree(self):
		next_node = 0
		self.visited_nodes[next_node] = 1
		while next_node != -1:
			(prev_node, next_node) = self.pick_next_node()
			if next_node != -1:
				self.mst[prev_node][next_node] = self.ratings[prev_node][next_node]
				self.mst[next_node][prev_node] = self.ratings[next_node][prev_node]
				self.visited_nodes[next_node] = 1

	def pick_next_node(self):
		min_weight = sys.maxsize
		prev_node = -1
		next_node = -1
		for from_node in range(self.num_chefs):
			if self.visited_nodes[from_node] == 1:
				for to_node in range(self.num_chefs):
					if from_node != to_node and self.visited_nodes[to_node] == 0:
						weight = self.ratings[from_node][to_node]
						if weight != 0 and weight < min_weight:
							min_weight = weight
							prev_node = from_node
							next_node = to_node
		return (prev_node, next_node)

	def get_sum_of_mst(self):
		sum = 0
		for row in self.mst:
			for num in row:
				sum += num
		return sum

	def write_answer(self):
		print(self.answer)

def main():
	solve()

def solve():
	num_problems = int(input())
	for num in range(num_problems):
		solve_problem()

def solve_problem():
	num_chefs = int(input())
	s = Solver(num_chefs)
	s.read_ratings()
	s.solve()
	s.write_answer()
main()


import sys
__Verbose__ = 0

def main():
	solve()

def print_header():
	print_log('-------------------------------------------------------------')
	print_log('-------------------- No unpaired chef -----------------------')
	print_log('-------------------------------------------------------------')

def print_log(*input):
	if __Verbose__ == 1:
		print(input)

def solve():
	num_problems = int(input())
	for num in range(num_problems):
		solve_problem()

def solve_problem():
	num_chefs = int(input())
	ratings = [[0 for x in range(num_chefs)] for y in range(num_chefs)]
	for num in range(num_chefs):
		ratings[num] = get_chef_rating(num_chefs)
	if num_chefs == 1:
		if ratings[0][0] == 0:
			print(-1)
		else:
			print(ratings[0][0])
		return
	(mst, visited_nodes) = get_minimum_spanning_tree(ratings)
	if sum(visited_nodes) != len(visited_nodes):
		print(-1)
	else:
		print(get_sum_of_matrix(mst))

def get_chef_rating(numChefs):
	chefRating = list(map(int, input().split()))
	if len(chefRating) != numChefs:
		raise ValueError(f'Expecting {numChefs} ratings; got {len(chefRating)}')
	return chefRating

def check_ratings(ratings):
	num_chefs = len(ratings)
	chef_a = 0
	for chefRating in ratings:
		if len(chefRating) != num_chefs:
			raise ValueError(f'Chef {chef_a} has not given rating to all chefs')
		for chef_b in range(len(chefRating)):
			if ratings[chef_a][chef_b] != ratings[chef_b][chef_a]:
				raise ValueError(f'Chef ratings is not symmetric {chef_a} {chef_b}')
			if ratings[chef_a][chef_b] < 0:
				raise ValueError(f'Chef rating is not a non-negative integer {chef_a} {chef_b}')
		chef_a += 1

def get_minimum_spanning_tree(matrix):
	num_nodes = len(matrix)
	mst = [[0 for x in range(num_nodes)] for y in range(num_nodes)]
	visited_nodes = [0] * num_nodes
	next_node = 0
	visited_nodes[next_node] = 1
	while next_node != -1:
		(prev_node, next_node) = pick_next_node(matrix, visited_nodes)
		if next_node != -1:
			mst[prev_node][next_node] = matrix[prev_node][next_node]
			mst[next_node][prev_node] = matrix[next_node][prev_node]
			visited_nodes[next_node] = 1
	return (mst, visited_nodes)

def pick_next_node(matrix, visited_nodes):
	min_weight = sys.maxsize
	prev_node = -1
	next_node = -1
	for from_node in range(len(visited_nodes)):
		if visited_nodes[from_node] == 1:
			for to_node in range(len(visited_nodes)):
				if from_node != to_node and visited_nodes[to_node] == 0:
					weight = matrix[from_node][to_node]
					if weight != 0 and weight < min_weight:
						min_weight = matrix[from_node][to_node]
						prev_node = from_node
						next_node = to_node
	return (prev_node, next_node)

def get_sum_of_matrix(matrix):
	sum = 0
	for row in matrix:
		for num in row:
			sum += num
	return sum
main()