Read problems statements in Mandarin Chinese and Russian as well. 

Andrii is a great programmer. He recently managed to enter Ukrainian IOI team. His parents wanted to appreciate him and present him a DAG(Directed Acyclic Graph). His favourite TV show is "Pimp My Ride" so he'd like to customize his graph. He'd like to add as many edges as possible in order to still have a DAG. Please, help Andrii, find the maximum number of edges he can add to his graph without obtaining any cycle. 
 
------ Input ------ 

The first line of an input contains single integer N — the number of vertices in the graph. Vertices are numerated from 1 to N. Next N lines contain N characters each — adjacency matrix of the graph. If there is '1' in j^{th} character of the i^{th} line then there is an edge from vertex i to vertex j in Andrii's graph. It's guaranteed that given graph does not contain cycles. 
 
------ Output ------ 

Output the maximal number of edges one can add to the graph in the first line. Then output the edges themselves. Edges should be written in separate lines, one by one. Edge is defined by a pair of integers a and b which means that edge from a to b should be added. 
The author is pretty lazy and he does not want to write checking program. So, if there are multiple solutions which lead to maximal number of edges that can be added, then you should output lexicographically smallest sequence of edges. A sequence of edges is smaller than another if the first edge that they differ in is lexicographically smaller. Edges are compared as pairs of integers, i.e. as sequence of two integers. 
 
------ Constraints ------ 

$1 ≤ N ≤ 1500$

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

Input:
3
010
000
000

Output:
2
1 3
2 3

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Directed graphs


Solutions:
(n, adj, newedge) = (int(input()), [], [])
(outdegree, used, count) = ({i: 0 for i in range(n)}, [0] * n, 0)
for _ in range(n):
	adj.append(list(str(input())))
	newedge.append([0] * len(adj[0]))
for i in range(n):
	outdegree[i] = adj[i].count('1')
for i in range(1, n + 1):
	for j in range(n - 1, -1, -1):
		if outdegree[j] == 0 and (not used[j]):
			v = j
			break
	used[j] = True
	for j in range(n):
		if j != v and (not int(adj[j][v])) and (not used[j]):
			newedge[j][v] = 1
			count += 1
	for j in range(n):
		if int(adj[j][v]):
			outdegree[j] -= 1
(x, y) = (len(newedge), len(newedge[0]))
print(count)
for i in range(x):
	for j in range(y):
		if newedge[i][j] == 1:
			print(i + 1, j + 1)


import heapq
import bisect

def heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)

def heappop_max(heap):
	lastelt = heap.pop()
	if heap:
		returnitem = heap[0]
		heap[0] = lastelt
		heapq._siftup_max(heap, 0)
		return returnitem
	return lastelt

def toposort(adj, degree, n, matrix):
	used = [0] * n
	order = []
	topo = []
	new = [[] for _ in range(n)]
	for i in range(n):
		if degree[i] == 0:
			heappush_max(order, i)
	count = 0
	while len(order) > 0:
		x = heappop_max(order)
		topo.append(x)
		for i in range(0, n):
			if matrix[i][x] == 0 and matrix[x][i] == 0 and (i != x):
				bisect.insort(new[i], x)
				matrix[i][x] = 1
				count += 1
			elif degree[i] > 0:
				degree[i] -= 1
				if degree[i] == 0:
					heappush_max(order, i)
	return (new, count)
n = int(input())
adj = [[] for _ in range(n)]
matrix = [[0 for i in range(n)] for j in range(n)]
ans = [[] for _ in range(n)]
degree = [0] * n
for i in range(n):
	c = 0
	for j in input():
		if int(j) == 1:
			adj[i].append(c)
		matrix[i][c] = int(j)
		c += 1
for i in range(n):
	degree[i] += len(adj[i])
(new, count) = toposort(adj, degree, n, matrix)
print(count)
for i in range(0, n):
	if len(new[i]) > 0:
		for j in new[i]:
			print(i + 1, j + 1)


n = int(input())
adj = []
for i in range(n):
	adj.append(list(map(int, input())))
outdegree = [0] * n
totaledge = n * (n - 1) // 2
for i in range(n):
	for j in range(n):
		if adj[i][j] == 1:
			outdegree[i] += 1
			totaledge -= 1
used = [False] * n
newedge = [[False] * n for i in range(n)]
for i in range(n):
	v = -1
	for j in range(n - 1, -1, -1):
		if not used[j] and outdegree[j] == 0:
			v = j
			break
	used[v] = True
	for j in range(n):
		if j != v and adj[j][v] == 0 and (not used[j]):
			newedge[j][v] = True
		if adj[j][v] == 1:
			outdegree[j] -= 1
print(totaledge)
for i in range(n):
	for j in range(n):
		if newedge[i][j]:
			print(i + 1, j + 1)


import sys
n = int(sys.stdin.readline())
nextEdge = [0] * n
for i in range(n):
	nextEdge[i] = sys.stdin.readline().strip()
out_degree = [0] * n
total_edges = n * (n - 1) // 2
for i in range(n):
	for j in range(n):
		if nextEdge[i][j] == '1':
			out_degree[i] += 1
			total_edges -= 1
used = [0] * n
newEdge = [[0] * n for i in range(n)]
for i in range(n):
	v = -1
	for j in range(n - 1, -1, -1):
		if not used[j] and out_degree[j] == 0:
			v = j
			break
	used[v] = True
	for j in range(n):
		if j != v and nextEdge[j][v] == '0' and (not used[j]):
			newEdge[j][v] = True
	for j in range(n):
		if nextEdge[j][v] == '1':
			out_degree[j] -= 1
print(total_edges)
for i in range(n):
	for j in range(n):
		if newEdge[i][j]:
			print(i + 1, j + 1)