Read problems statements in Mandarin Chinese and Russian as well. 

After IOI Ilya decided to make a business.  He found a social network called "TheScorpyBook.com". It currently has N registered users. As in any social network two users can be friends. Ilya wants the world to be as connected as possible, so he wants to suggest friendship to some pairs of users. He will suggest user u to have a friendship with user v if they are not friends yet and there is a user w who is friends of both of them. Note that u, v and w are different users. Ilya is too busy with IPO these days, so he asks you to count how many friendship suggestions he has to send over his social network.
 
------ Input ------ 

The first line contains an integer number N — the number of users in the network. Next N lines contain N characters each denoting friendship relations. j^{th} character if the i^{th} lines equals one, if users i and j are friends and equals to zero otherwise. This relation is symmetric, i.e. if user a is friend of b then b is also a friend of a.
 
------ Output ------ 

Output a single integer — number of friendship suggestions Ilya has to send.
 
------ Constraints ------ 

$1 ≤ N ≤ 2000$

------ Example ------ 

Input:
4
0111
1000
1000
1000

Output:
6

------ Explanation ------ 

Each of users [2, 3, 4] should receive two friendship suggestions, while user 1 does not need any, since he already has all other users in his friend-list.

Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Data structures

Mathematics
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
n = int(input())
vertex = [input() for x in range(n)]
friendship = [int(x, 2) for x in vertex]
limit = 0
count = 0
for i in range(n):
	for j in range(limit):
		if vertex[i][j] == '0' and i != j and friendship[i] & friendship[j]:
			count += 2
	limit += 1
print(count)


try:
	l = int(input())
	arr = []
	rows = []
	count = 0
	for _ in range(l):
		temp = input()
		arr.append(int(temp, 2))
		rows.append(list(temp))
	for i in range(l):
		for j in range(i + 1, l):
			if rows[i][j] == '0':
				if arr[i] & arr[j] > 0:
					count += 2
	print(count)
except:
	pass


a = []
b = []
n = int(input())
for _ in range(n):
	inp = input()
	a.append(inp)
	b.append(int(inp, 2))
sum = 0
for i in range(n):
	for j in range(i + 1, n):
		if a[i][j] == '0' and b[i] & b[j]:
			sum += 1
print(sum * 2)


import sys
N = int(sys.stdin.readline())
grid = [0] * N
compare = [0] * N
ans = 0
for i in range(N):
	grid[i] = sys.stdin.readline()
	compare[i] = int(grid[i], 2)
for i in range(N):
	for j in range(i):
		if grid[i][j] == '0':
			if compare[i] & compare[j]:
				ans += 2
print(ans)


import sys
n = int(sys.stdin.readline())
adj_mat = []
ints = []
for ln_i in range(n):
	adj_mat.append(sys.stdin.readline())
	ints.append(int(adj_mat[ln_i], 2))
requests = 0
for i in range(n):
	for j in range(i):
		if adj_mat[i][j] == '0':
			if ints[i] & ints[j]:
				requests += 2
sys.stdout.write(str(requests) + '\n')


from math import ceil, sqrt, log, gcd
from collections import deque, defaultdict as dd
from os import path
import sys
t = int(input())
a = []
adj = []
z = 0
for f in range(t):
	s = input()
	adj.append(s)
	a.append(int(s, 2))
for u in range(t):
	for v in range(u + 1, t):
		if adj[u][v] == '0' and a[u] & a[v]:
			z += 2
print(int(z))


n = int(input())
friend_list = []
bin = []
for i in range(n):
	r = input()
	friend_list.append(r)
	bin.append(int(r, 2))
count = 0
for i in range(n):
	for j in range(i + 1, n):
		if friend_list[i][j] == '0' and bin[i] & bin[j]:
			count += 1
print(count * 2)


def check(a, b, n):
	if a & b:
		return True
	return False
n = int(input())
l = []
ll = []
for _ in range(n):
	x = input()
	l.append(list(x))
	ll.append(int(x, 2))
req = 0
for i in range(n):
	for j in range(1 + i, n):
		if l[i][j] == '0' and check(ll[i], ll[j], n):
			req += 1
print(2 * req)


t = int(input())
l = []
l1 = []
for i in range(t):
	s = input()
	l.append(s)
	l1.append(int(s, 2))
j = 0
k = 0
cout = 0
while j < t - 1:
	k = j + 1
	while k < t:
		if l[j][k] == '0' and l1[j] & l1[k] >= 1:
			cout = cout + 2
		k = k + 1
	j = j + 1
print(cout)


n = int(input())
l = []
l2 = []
c = 0
m = []
for i in range(n):
	f = input()
	sub = set()
	l3 = ['0' * (8 - len(x)) + x for x in f]
	l2.append(l3)
	m.append(int(f, 2))
for i in range(n - 1):
	for j in range(i + 1, n):
		if l2[i][j][-1] == '0' and m[i] & m[j] != 0:
			c += 2
print(c)


a = int(input())
c = []
d = []
for i in range(a):
	now = input()
	c.append(now)
	d.append(int(now, 2))
i = 0
for k in range(a):
	for j in range(k + 1, a):
		if c[k][j] != '1':
			if int(d[k]) & int(d[j]):
				i = i + 2
print(i)


import sys
i = int(sys.stdin.readline())
arr = []
comp = [0] * i
count = 0
for _ in range(i):
	p = input()
	arr.append(list(p))
	comp[_] = int(p, 2)
for t in range(i):
	for a in range(t):
		if arr[t][a] == '0':
			if comp[t] & comp[a]:
				count += 2
print(count)


n = int(input())
string = []
binary = []
for i in range(n):
	inp = input()
	string.append(inp)
	binary.append(int(inp, 2))
count = 0
for i in range(n):
	for j in range(i + 1, n):
		if string[i][j] == '0' and binary[i] & binary[j]:
			count += 1
print(count * 2)


n = int(input())
arr = []
a = []
for a0 in range(n):
	arr.append(input())
for i in arr:
	a.append(int(i, base=2))
ans = 0
for i in range(len(a) - 1):
	for j in range(i + 1, len(a)):
		if arr[i][j] == '0':
			if a[i] & a[j] != 0:
				ans += 2
print(ans)


t = int(input())
a = []
adj = []
for i in range(t):
	s = input()
	adj.append(s)
	a.append(int(s, 2))
z = 0
for u in range(t):
	for v in range(u + 1, t):
		if adj[u][v] == '0' and a[u] & a[v]:
			z += 2
print(int(z))


N = int(input())
matrix = []
is_friend = []
for i in range(0, N):
	row = []
	line = input()
	is_friend.append(line)
	matrix.append(int(line, 2))
count = 0
for i in range(0, N):
	for j in range(i + 1, N):
		if is_friend[i][j] != '1' and matrix[i] & matrix[j] > 0:
			count += 2
print(count)


adj = []
a = []
f = 0
n = int(input())
for i in range(n):
	s = input()
	adj.append(list(s))
	a.append(int(s, 2))
for i in range(n):
	for j in range(i + 1, n):
		if adj[i][j] == '0' and a[i] & a[j] != 0:
			f += 2
print(f)


n = int(input())
a = [[0 for _ in range(n)] for _ in range(n)]
bi = [0 for _ in range(n)]
for i in range(n):
	k = input()
	a[i] = k
	bi[i] = int(k, 2)
count = 0
for i in range(n):
	for j in range(i + 1, n):
		if a[i][j] == '0':
			if bi[i] & bi[j]:
				count += 1
print(count * 2)


def requestPending():
	n = int(input())
	bitset = []
	nums = []
	for i in range(n):
		bitset.append(input())
		nums.append(int(bitset[i], 2))
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if bitset[i][j] == '0' and nums[i] & nums[j] != 0:
				count += 2
	print(count)
requestPending()


n = int(input())
arr = []
adj = []
for i in range(n):
	k = input()
	adj.append(k)
	arr.append(int(k, 2))
count = 0
for i in range(n):
	for j in range(i + 1, n):
		if adj[i][j] == '0' and arr[i] & arr[j]:
			count += 1
print(int(count * 2))


n = int(input())
array = [input() for i in range(n)]
frndship = [int(x, 2) for x in array]
count = 0
limit = 0
for i in range(n):
	for j in range(limit):
		if array[i][j] == '0' and i != j and frndship[i] & frndship[j]:
			count += 2
	limit += 1
print(count)


total = 0
friends = int(input())
adjmat = [0] * friends
binreps = [0] * friends
for line in range(friends):
	sa = input()
	adjmat[line] = sa
	binreps[line] = int(sa, 2)
for i in range(friends - 1):
	for j in range(i + 1, friends):
		if adjmat[i][j] != '1':
			if binreps[i] & binreps[j] != 0:
				total += 2
print(total)


n = int(input())
a = []
b = []
for i in range(n):
	k = input()
	b.append(k)
	a.append(int(k, 2))
cnt = 0
for i in range(n):
	for j in range(i + 1, n):
		if b[i][j] == '0' and a[i] & a[j]:
			cnt += 1
print(int(cnt * 2))


n = int(input())
relMatrix = []
binArray = []
suggConn = 0
for i in range(0, n):
	binValues = ['{0:04b}'.format(int(x)) for x in input()]
	relMatrix.append(binValues)
	binArray.append(int(''.join(binValues), 2))
for i in range(0, n):
	for j in range(i, n):
		if i != j and int(relMatrix[i][j]) == 0:
			if binArray[i] & binArray[j] != 0:
				suggConn += 2
print(suggConn)


n = int(input())
B = []
for _ in range(n):
	x = input()
	B.append(int(x, 2))
count = 0
J = 1 << n
for i in range(n):
	j = 1
	p = n - 1
	while j != J:
		if p == i:
			j <<= 1
			p -= 1
			continue
		if not B[i] & j:
			if B[i] & B[p]:
				count += 1
		j <<= 1
		p -= 1
print(count)


n = int(input())
l = []
l2 = []
c = 0
m = []
for i in range(n):
	f = input()
	sub = set()
	l2.append(f)
	m.append(int(f, 2))
for i in range(n - 1):
	for j in range(i + 1, n):
		if l2[i][j] == '0' and m[i] & m[j] != 0:
			c += 2
print(c)


a = []
b = []
res = 0
n = int(input())
for i in range(n):
	s = input()
	a.append(list(s))
	b.append(int(s, 2))
for i in range(n):
	for j in range(i + 1, n):
		if a[i][j] == '0' and b[i] & b[j] != 0:
			res += 1
print(res * 2)


try:
	n = int(input())
	store = []
	st = []
	for i in range(n):
		m = input()
		store.append(m)
		st.append(int(m, 2))
	res = 0
	for i in range(n):
		for j in range(i + 1, n):
			if store[i][j] == '0' and st[i] & st[j] > 0:
				res += 2
	print(res)
except:
	pass


a = []
b = []
res = 0
try:
	n = int(input())
except EOFError:
	exit(0)
for i in range(n):
	s = input()
	a.append(list(s))
	b.append(int(s, 2))
for i in range(n):
	for j in range(i + 1, n):
		if a[i][j] == '0' and b[i] & b[j] != 0:
			res += 1
print(res * 2)