The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign R Rebel spaceships to guard B bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision.


-----Input-----

The first line contains two space-separated integers R, B(1 ≤ R, B ≤ 10). For 1 ≤ i ≤ R, the i + 1-th line contains two space-separated integers x_{i} and y_{i} (|x_{i}|, |y_{i}| ≤ 10000) denoting the coordinates of the i-th Rebel spaceship. The following B lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line.


-----Output-----

If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).


-----Examples-----
Input
3 3
0 0
2 0
3 1
-2 1
0 3
2 2

Output
Yes

Input
2 1
1 0
2 2
3 1

Output
No



-----Note-----

For the first example, one possible way is to connect the Rebels and bases in order.

For the second example, there is no perfect matching between Rebels and bases.

Difficulty: MEDIUM_HARD
Tags: Geometry

Complete search

Mathematics

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
def check(a, b):
	ansa = b[0] - a[0]
	ansb = b[1] - a[1]
	return [ansa, ansb]
while True:
	try:
		(n, m) = map(int, input().split())
		if n != m:
			a = list()
			b = list()
			for i in range(n):
				a.append(list(map(int, input().split())))
			for i in range(m):
				b.append(list(map(int, input().split())))
			print('No')
		else:
			a = list()
			b = list()
			for i in range(n):
				a.append(list(map(int, input().split())))
			for i in range(m):
				b.append(list(map(int, input().split())))
			flag = False
			for i in range(len(a)):
				for j in range(i + 1, len(a)):
					for k in range(len(b)):
						for l in range(k + 1, len(b)):
							ansa = check(a[i], a[j])
							ansb = check(a[i], b[k])
							ansc = check(a[i], b[l])
							if ansa[0] == ansb[0] and ansa[0] == ansc[0] and (ansa[0] == 0) or (ansa[0] != 0 and ansb[0] != 0 and (ansc[0] != 0) and (ansa[1] / ansa[0] == ansb[1] / ansb[0]) and (ansa[1] / ansa[0] == ansc[1] / ansc[0])):
								print('No')
								flag = True
								break
							else:
								continue
						if flag == True:
							break
					if flag == True:
						break
				if flag == True:
					break
			if flag == False:
				print('Yes')
	except EOFError:
		break


(a, b) = list(map(int, input().split()))
if a == b:
	print('Yes')
else:
	print('No')


print(('No', 'Yes')[len(set(input().split())) == 1])


(b, r) = input().split()
for x in range(int(b)):
	(temp, temp) = input().split()
for x in range(int(r)):
	(temp, temp) = input().split()
if b == r:
	print('Yes')
else:
	print('No')


(r, b) = [int(i) for i in input().split()]
for i in range(r):
	discard = [int(i) for i in input().split()]
print('Yes' if r == b else 'No')


(n, m) = map(int, input().split())
if n == m:
	print('YES')
else:
	print('NO')


from decimal import *
getcontext().prec = 16
from math import sqrt
(R, B) = list(map(int, input().split(' ')))
for i in range(R):
	useless = input()
for j in range(B):
	useless = input()
if R == B:
	print('YES')
else:
	print('NO')


s = input()
in1 = s.split(' ')
R = int(in1[0])
B = int(in1[1])
print('Yes' if R == B else 'No')


(r, b) = list(map(int, input().split()))
if r == b:
	print('Yes')
else:
	print('No')


(n, m) = [int(x) for x in input().split()]
for i in range(n + m):
	s = input()
if n == m:
	print('Yes')
else:
	print('No')


(a, b) = map(int, input().split())
for i in range(a + b):
	(n, m) = map(int, input().split())
if a == b:
	print('Yes')
else:
	print('No')


def ccw(A, B, C):
	return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0])

def intersect(A, B, C, D):
	return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)
(R, B) = map(int, input().split())
rs = []
bs = []
for r in range(R):
	rs.append(list(map(int, input().split())))
for r in range(B):
	bs.append(list(map(int, input().split())))
if R != B:
	print('No')
else:

	def rec(at, done, remain):
		if at >= B:
			return True
		for b in remain:
			for (r, d) in zip(rs, done):
				if intersect(r, bs[d], rs[at], bs[b]):
					break
			else:
				ok = rec(at + 1, done + [b], remain - {b})
				if ok:
					return True
		return False
	print(['NO', 'YES'][rec(0, [], set(range(B)))])


from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	print(('No', 'Yes')[len(set(input().split())) == 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(x, y) = list(map(int, input().split()))
for k in range(x + y):
	a = input()
if x == y:
	print('Yes')
else:
	print('No')


(R, B) = list(map(int, input().split()))
print(('No', 'Yes')[R == B])


(a, b) = map(int, input().split())
if a == b:
	print('YES')
else:
	print('NO')


(n, m) = map(int, input().split())
for i in range(n):
	(x, y) = map(int, input().split())
for i in range(m):
	(x, y) = map(int, input().split())
print('Yes' if n == m else 'No')


(R, B) = map(int, input().split())
for i in range(R + B):
	x = input()
if R == B:
	print('Yes')
else:
	print('No')


(r, b) = map(int, input().split())
for i in range(r + b):
	l = input().split()
if r == b:
	print('Yes')
else:
	print('No')


(n, m) = map(int, input().split())
for i in range(n + m):
	a = input()
if n == m:
	print('YES')
else:
	print('NO')


a = input().split()
if a[0] == a[1]:
	print('YES')
else:
	print('NO')


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
for i in range(n):
	(a, b) = map(int, input().split())
for i in range(k):
	(a, b) = map(int, input().split())
if n == k:
	print('YES')
else:
	print('NO')


l = input().split(' ')
print('Yes' if int(l[0]) == int(l[1]) else 'No')


(r, b) = map(int, input().split())
print(('No', 'Yes')[r == b])


str1 = input()
l_1 = str1.split(' ')
tedad = int(l_1[0])
tedad1 = int(l_1[1])
for i in range(tedad):
	n = input()
for i in range(tedad1):
	n = input()
if tedad1 == tedad:
	print('Yes')
else:
	print('No')


(x, y) = map(int, input().split())
if x == y:
	print('Yes')
else:
	print('No')


(R, B) = map(int, input().split())
if R == B:
	print('yes')
else:
	print('no')