Johnny has a pool in his garden. There are several islands in the pool. Some islands are connected by bridges. Any bridge can be removed. Every day Johnny removes some bridges so that there is only one way from any island to any other. In the evening he returns removed bridges to their places. Also he has some favorite bridges which he never removes. Johnny will be happy if he is able to make a configuration of bridges on the given day which he has never made before. You have to count the amount of days he will be happy. Of course, if the favorite bridges themselves don't satisfy the happiness condition Johnny will not be happy for even single day.

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

The first line of input file contains number t – the number of test cases. Then the description of each test case follows. The first line of each test case contains number n – the number of islands. Islands are numbered with integers from 1 to n. Then n lines follow each containing n characters defining the connectivity matrix of those islands. Character in column x of line y will be ‘1’ if the islands with numbers x and y are connected and ‘0’ otherwise. The next line is number p – the number of favorite bridges. The next p lines contain the pairs of islands that are connected by favorite bridges.

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

For each test case print the number of days Johnny will be happy in this situation.

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

1 ≤ t ≤ 5

2 ≤ n ≤ 30

1 ≤ p ≤ min(6, n-1)

----- Sample Input 1 ------ 
1
4
0111
1011
1101
1110
2
1 2
3 4
----- Sample Output 1 ------ 
4

Difficulty: HARD
Tags: Graph algorithms

Spanning trees

Combinatorics

Mathematics

Matrices

Starter code:

Solutions:
from fractions import Fraction

def determinant(mat):
	res = Fraction(1, 1)
	n = len(mat)
	for i in range(n):
		if mat[i][i] == Fraction(0):
			for j in range(i + 1, n):
				if mat[j][i] != Fraction(0):
					swap(mat[i][j])
					res *= -1.0
					break
		if mat[i][i] == 0:
			return Fraction(0)
		res *= mat[i][i]
		for j in range(i + 1, n):
			f = Fraction(1) * mat[j][i] / mat[i][i]
			for k in range(i, n):
				mat[j][k] -= f * mat[i][k]
	return res

class UnionFind:

	def __init__(self, maxSize):
		self.parent = [i for i in range(maxSize)]
		self.treeHeight = [1 for i in range(maxSize)]
		self.treeSize = [1 for i in range(maxSize)]

	def find(self, x):
		root = x
		while self.parent[root] != root:
			root = self.parent[root]
		climbingNode = x
		while climbingNode != root:
			temp = self.parent[climbingNode]
			self.parent[climbingNode] = root
			climbingNode = temp
		return root

	def union(self, x, y):
		rootX = self.find(x)
		rootY = self.find(y)
		if self.treeHeight[rootX] < self.treeHeight[rootY]:
			(rootX, rootY) = (rootY, rootX)
		if self.treeHeight[rootX] == self.treeHeight[rootY]:
			self.treeHeight[rootX] += 1
		self.parent[rootY] = rootX
		self.treeSize[rootX] += self.treeHeight[rootY]
t = int(input())
for tests in range(t):
	n = int(input())
	graph = []
	for i in range(n):
		graph.append(list(map(int, list(input().strip()))))
	unf = UnionFind(n)
	m = int(input())
	notPossible = False
	favs = []
	for i in range(m):
		favs.append(list(map(int, list(input().strip().split()))))
	for i in range(m):
		(a, b) = favs[i]
		if unf.find(a - 1) == unf.find(b - 1):
			notPossible = True
			break
		unf.union(a - 1, b - 1)
	if notPossible:
		print(0)
		continue
	parent = [unf.find(i) for i in range(n)]
	parent.sort()
	indices = [parent[0]]
	for i in parent[1:]:
		if i != indices[-1]:
			indices.append(i)
	newSize = len(indices)
	newGraph = [[0 for i in range(newSize)] for j in range(newSize)]
	for i in range(n):
		for j in range(n):
			if graph[i][j] == 1 and unf.find(i) != unf.find(j):
				newGraph[indices.index(unf.find(i))][indices.index(unf.find(j))] -= 1
	if newSize == 1:
		print(1)
		continue
	for i in range(newSize):
		newGraph[i][i] = -1 * sum(newGraph[i])
	newGraph.pop()
	for i in range(len(newGraph)):
		newGraph[i].pop()
	for i in range(len(newGraph)):
		for j in range(len(newGraph)):
			newGraph[i][j] = Fraction(newGraph[i][j], 1)
	ans = int(determinant(newGraph))
	print(ans)