Read problems statements in Mandarin Chinese here

City of Byteland can be described as a $2D$ grid of cells. Each cell may or may not contain a demon. You are given the list of cells that contain demons.

In a single Kamehameha attack, Goku can kill all the demons standing in a row or in a column. But using Kamehameha drains Goku's power. You are to tell the minimum number of Kamehameha attacks that will be required by Goku to destroy all the demons.

------  Input ------
The first line contains a single integer $T$, the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $N$, the number of cells where enemies are present. The description of the enemies follows.
The next $N$ lines contain two space separated integers $X$ and $Y$, the row and column of the cell in which a demon is present.

------  Output ------
For each test case, on a new line, print the minimum number of attacks that are required to kill all of the demons.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 1000$
$1 ≤ X, Y ≤ 10^{9}$

----- Sample Input 1 ------ 
1
3
0 0
1 0
0 1
----- Sample Output 1 ------ 
2

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Data structures

Combinatorics

Flows and cuts


Solutions:
import sys

def Max_R(i):
	return len(R[i])

def Max_C(i):
	return len(C[i])
T = int(sys.stdin.readline())
Ans = ''
for t in range(T):
	R = {}
	C = {}
	N = int(sys.stdin.readline())
	ans = 0
	for i in range(N):
		(x, y) = map(int, sys.stdin.readline().split())
		if x in R:
			R[x] += [y]
		else:
			R[x] = [y]
		if y in C:
			C[y] += [x]
		else:
			C[y] = [x]
	while N > 0:
		ans += 1
		x = sorted(R, key=Max_R, reverse=True)
		y = sorted(C, key=Max_C, reverse=True)
		xx = False
		ix = 0
		iy = 0
		yy = False
		for i in range(len(R)):
			X = R[x[i]]
			for item in X:
				if len(C[item]) == 1:
					xx = True
					ix = x[i]
					break
			if xx == True:
				break
		for i in range(len(C)):
			Y = C[y[i]]
			for item in Y:
				if len(R[item]) == 1:
					iy = y[i]
					yy = True
					break
			if yy == True:
				break
		if xx == True:
			N -= len(X)
			for item in X:
				C[item].remove(ix)
				if C[item] == []:
					del C[item]
			del R[ix]
		elif yy == True:
			N -= len(Y)
			for item in Y:
				R[item].remove(iy)
				if R[item] == []:
					del R[item]
			del C[iy]
		else:
			ans += min(len(R), len(C)) - 1
			break
	Ans += str(ans) + '\n'
sys.stdout.write(Ans)