Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

College admissions are starting and Chef has also recently completed his high school. There are $N$ colleges, numbered from $1$ to $N$, and they are ranked from $1$ to $N$. Each college has only a single seat left. To apply for the colleges, every student has to give a common exam, the result of which decides their destiny, i.e, the student having best rank (scoring max marks) gets to choose the college of their preference first. 

Each student has a list of colleges that they like. They will want to get to the best-ranked college from their list. If they can't get into it, they will want to get into the second-ranked college from among their list, and so on.

If the single vacant seat of a college gets filled, the admission for that year is closed in that college. Then, the people who have applied for that college have to look for a lower-ranked college in their preference list provided that it still has vacancies.

Given information about $M$ students, about their marks scored in the exam (given as ranks) and the id’s of the college they are applying for, find which college Chef will land into given that he is the student with $id = 1$.

Every student tries to get into the highest-ranked college on his list which has a vacancy and if not possible to get into any of the colleges on his list, he won’t join any college this year.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains $M + 3$ lines of input.
First line contains $2$ space separated integers $N$, $M$, the total number of colleges, and total number of students respectively.
Second line contain $N$ distinct space separated integers $R_{i}$, rank of the $i^{th}$ college. Here $1$ denotes a higher rank and $N$ denotes a lower rank.
Third line contains $M$ distinct space separated integers $S_{i}$, the rank of the $i^{th}$ student in the exam. Here $1$ denotes a higher rank, i.e, maximum marks scored and $M$ denotes a lower rank, i.e, minimum marks scored.
Next $M$ lines contain $K + 1$ space separated integers which the first integer $K$ is the number of colleges $i^{th}$ student will apply to and the next $K$ integers describe the same.

------ Output: ------
For each testcase, output in a single line the college in which Chef applies and $0$ if he won't be joining any college this year.

------ Constraints  ------
$1 ≤ N, M ≤ 5*10^{4}$
$R$ is the permutation of integers from $[1, N]$
$S$ is the permutation of integers from $[1, M]$
Sum of $N$ over all tests is atmost $3* 10^{5}$
Sum of $M$ over all tests is atmost $3.5 * 10^{5}$
Sum of $K$ over all students over all tests is atmost $1.5*10^{6}$
Every student applies to atleast $1$ college and all the applied colleges are different.

Note: Language multiplier for $Java$ is $3$ and for $python$ is $5$ and its recommended to use Fast Input-Output for this problem.

----- Sample Input 1 ------ 
3

2 2

2 1

1 2

2 1 2

2 1 2

1 2

1

2 1

1 1

1 1

2 1

1 2

1

2 2 1
----- Sample Output 1 ------ 
2

0

1
----- explanation 1 ------ 
Case 1: Here since Chef has the highest rank, he gets to choose the highest rank college in his preference list first, that is college with $id = 2$.

Case 2: Here since there is only $1$ college and Chef stood second, he won't be able to apply to any of the colleges this year, so we print $id = 0$.

Case 3: Here since Chef is the only student and thus has the highest rank, he gets to choose the highest rank college in his preference list first, that is college with $id = 1$.

Difficulty: VERY_HARD
Tags: Mathematics

Sorting

Implementation

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
for i in range(int(input())):
	(X, P) = map(int, input().split())
	crank = list(map(int, input().split()))
	srank = list(map(int, input().split()))
	student = []
	for i in range(P):
		c = list(map(int, input().split()))
		_c = sorted(c[1:], key=lambda x: crank[x - 1])
		student.append([i, c[0], _c])
	sortstudent = sorted(student, key=lambda x: srank[x[0]])
	clgs_filed = [False] * X
	choice = 0
	for i in sortstudent:
		ch = 0
		for j in i[2]:
			if clgs_filed[j - 1] == False:
				clgs_filed[j - 1] = True
				ch = j
				break
		if i[0] == 0:
			choice = ch
			break
	print(choice)


for i in range(int(input())):
	(X, P) = map(int, input().split())
	cRank = list(map(int, input().split()))
	sRank = list(map(int, input().split()))
	student = []
	for i in range(P):
		c = list(map(int, input().split()))
		_c = sorted(c[1:], key=lambda x: cRank[x - 1])
		student.append([i, c[0], _c])
	sort_student = sorted(student, key=lambda x: sRank[x[0]])
	clgs_filed = [False] * X
	choice = 0
	for i in sort_student:
		ch = 0
		for j in i[2]:
			if clgs_filed[j - 1] == False:
				clgs_filed[j - 1] = True
				ch = j
				break
		if i[0] == 0:
			choice = ch
			break
	print(choice)


for i in range(int(input())):
	(u, p) = map(int, input().split())
	cR = list(map(int, input().split()))
	liste = list(map(int, input().split()))
	student = []
	for i in range(p):
		c = list(map(int, input().split()))
		_c = sorted(c[1:], key=lambda u: cR[u - 1])
		student.append([i, c[0], _c])
	sort_stu = sorted(student, key=lambda u: liste[u[0]])
	cls_filed = [False] * u
	cho = 0
	for i in sort_stu:
		ch = 0
		for j in i[2]:
			if cls_filed[j - 1] == False:
				cls_filed[j - 1] = True
				ch = j
				break
		if i[0] == 0:
			cho = ch
			break
	print(cho)


for i in range(int(input())):
	(N, M) = map(int, input().split())
	cRank = list(map(int, input().split()))
	sRank = list(map(int, input().split()))
	students = []
	for i in range(M):
		c = list(map(int, input().split()))
		_c = sorted(c[1:], key=lambda x: cRank[x - 1])
		students.append([i, c[0], _c])
	sort_students = sorted(students, key=lambda x: sRank[x[0]])
	clgs_filed = [False] * N
	choice = 0
	for i in sort_students:
		ch = 0
		for j in i[2]:
			if clgs_filed[j - 1] == False:
				clgs_filed[j - 1] = True
				ch = j
				break
		if i[0] == 0:
			choice = ch
			break
	print(choice)


t = int(input())
for i in range(0, t):
	(K, L) = map(int, input().split())
	aRank = [int(x) for x in input().split()]
	bRank = [int(x) for x in input().split()]
	students = []
	for i in range(L):
		a = [int(x) for x in input().split()]
		_a = sorted(a[1:], key=lambda x: aRank[x - 1])
		students.append([i, a[0], _a])
	sort_students = sorted(students, key=lambda x: bRank[x[0]])
	clgs_filed = [False] * K
	choice = 0
	for i in sort_students:
		ch = 0
		for j in i[2]:
			if clgs_filed[j - 1] == False:
				clgs_filed[j - 1] = True
				ch = j
				break
		if i[0] == 0:
			choice = ch
			break
	print(choice)


t = int(input())
while t != 0:
	(n, m) = list(map(int, input().split()))
	coll = list(map(int, input().split()))
	stud = list(map(int, input().split()))
	pref = []
	for i in range(m):
		c = list(map(int, input().split()))
		_c = sorted(c[1:], key=lambda x: coll[x - 1])
		pref.append(_c)
	allot = [0] * n
	top_stud = []
	for i in range(m):
		top_stud.append(i)
	top_stud = sorted(top_stud, key=lambda x: stud[x])
	for i in top_stud:
		flag = 0
		j = 0
		while j < len(pref[i]):
			if allot[pref[i][j] - 1] == 0:
				flag = 1
				allot[pref[i][j] - 1] = 1
				if i == 0:
					print(pref[i][j])
				break
			else:
				j += 1
		if i == 0:
			if flag == 0:
				print(0)
			break
	t -= 1


import io, os, time
start = time.perf_counter()
CHEF_ID = 1
ADMITED = 100000
for tc in range(int(input())):
	(nColl, mStud) = map(int, input().split())
	rColl = [ADMITED] + list(map(int, input().split()))
	rStud = [ADMITED] + list(map(int, input().split()))
	arrStudColl = [[]]
	for st in range(mStud):
		w = list(map(int, input().split()))
		arrStudColl.append(w[1:w[0] + 1])
	studByRate = [-1] * (mStud + 1)
	for stud in range(1, mStud + 1):
		studByRate[rStud[stud]] = stud
	collLeft = nColl
	for studId in studByRate[1:mStud + 1]:
		maxRateOfColl = ADMITED
		for collId in arrStudColl[studId]:
			if rColl[collId] < maxRateOfColl:
				maxRateOfColl = rColl[collId]
				maxRateCollId = collId
		if studId == CHEF_ID:
			if maxRateOfColl == ADMITED:
				print(0)
			else:
				print(maxRateCollId)
			break
		if maxRateCollId != ADMITED:
			rColl[maxRateCollId] = ADMITED
			collLeft + -1
			if collLeft == 0:
				print(0)
				break


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	rank_col = list(map(int, input().split()))
	rank_stud = list(map(int, input().split()))
	college = []
	map_college = {}
	for i in range(n):
		college.append((rank_col[i], i + 1))
		map_college[i + 1] = rank_col[i]
	college.sort()
	stud = []
	for i in range(m):
		l = list(map(int, input().split()))
		stud.append((rank_stud[i], i, l[1:]))
	stud.sort()
	for (rank, ind, list_of_c) in stud:
		if ind == 0:
			best_r = n * 2
			best_col_id = 0
			for i in range(len(list_of_c)):
				col_id = list_of_c[i]
				if map_college[col_id] != -1:
					cur_r = map_college[col_id]
					if best_r > cur_r:
						best_r = cur_r
						best_col_id = col_id
			map_college[best_col_id] = -1
			print(best_col_id)
			break
		else:
			best_r = n * 2
			best_col_id = 0
			for i in range(len(list_of_c)):
				col_id = list_of_c[i]
				if map_college[col_id] != -1:
					cur_r = map_college[col_id]
					if best_r > cur_r:
						best_r = cur_r
						best_col_id = col_id
			map_college[best_col_id] = -1


clg_choice = []
clg_rank_new = []
testcases = int(input())
for i in range(testcases):
	clg_choice.clear()
	clg_rank_new.clear()
	no_clg = int(0)
	(N_of_clg, M_of_students) = map(int, input().split())
	clg_rank = list(map(int, input().split()))
	clg_rank = [[clg_rank[i], i + 1, 0] for i in range(N_of_clg)]
	students_rank = list(map(int, input().split()))
	chef_rank = students_rank[0]
	students_rank = [[students_rank[i], i + 1, 0] for i in range(M_of_students)]
	for i in range(M_of_students):
		clg_choice.append(list(map(int, input().split())))
		clg_choice[i][0] = 0
	students_rank.sort()
	for j in range(1, len(clg_choice[0])):
		clg_rank[clg_choice[0][j] - 1][2] = 1
		clg_rank_new.append(clg_rank[clg_choice[0][j] - 1])
	clg_rank_new.sort()
	for i in range(len(clg_choice[0]) - 1):
		no_clg = clg_rank_new[i][1]
		for j in range(chef_rank - 1):
			if students_rank[j][2] == 0:
				if clg_rank_new[i][1] in clg_choice[students_rank[j][1] - 1]:
					students_rank[j][2] = 1
					if i + 1 == len(clg_choice[0]) - 1:
						no_clg = 0
					else:
						no_clg = clg_rank_new[i + 1][1]
					break
		if no_clg == clg_rank_new[i][1]:
			break
	print(no_clg)
	students_rank.clear()
	clg_rank.clear()


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	R = list(map(int, input().split()))
	S = list(map(int, input().split()))
	l = []
	h = {}
	for i in range(M):
		K = list(map(int, input().split()))
		K = K[1:]
		K.sort(key=lambda x: R[x - 1])
		l.append([K, i + 1])
	l.sort(key=lambda x: S[x[1] - 1])
	a = 0
	for i in range(M):
		x = 0
		for j in l[i][0]:
			if h.get(j):
				continue
			else:
				h[j] = 1
				x = j
				break
		if l[i][1] == 1:
			a = x
			break
	print(a)


tot = int(input())
for _ in range(tot):
	ans = None
	(N, M) = list(map(int, input().split()))
	CR = input()
	SR = list(map(int, input().split()))
	SP = []
	filled = [0] * (N + 1)
	for _ in range(M):
		sp_temp = list(map(int, input().split()))
		SP.append(sp_temp)
	chefRank = SR[0]
	(SR, SP) = [list(t) for t in zip(*sorted(zip(SR, SP)))]
	for (i, rank) in enumerate(SR):
		if rank != chefRank:
			for pref in SP[i][1:]:
				if filled[pref] == 0:
					filled[pref] = 1
					break
		else:
			for pref in SP[i][1:]:
				if filled[pref] == 0:
					ans = pref
					print(ans)
					break
			if ans == None:
				print(0)
				break
			break


t = int(input())
while t != 0:
	(n, m) = list(map(int, input().split()))
	collegeRank = list(map(int, input().split()))
	studentsRank = list(map(int, input().split()))
	chefsRank = studentsRank[0]
	studentPreferences = [[-1]] * (chefsRank + 1)
	for i in range(m):
		CurrentStudentRank = studentsRank[i]
		studentsPreference = list(map(int, input().split()))
		if CurrentStudentRank <= chefsRank:
			studentPreferences[CurrentStudentRank] = studentsPreference
	studentsRank.sort()
	if n < chefsRank:
		print('0')
	else:
		chefsPreferences = studentPreferences[chefsRank]
		chefsPreferences = chefsPreferences[1:]
		j = 1
		while j <= chefsRank:
			currentPreference = studentPreferences[j]
			currentPreference = currentPreference[1:]
			commonPreferences = list(set(chefsPreferences) & set(currentPreference))
			maxRank = 0
			if len(commonPreferences) > 0:
				ranking = []
				for i in range(len(commonPreferences)):
					currentCollageRank = collegeRank[commonPreferences[i] - 1]
					if currentCollageRank != -1:
						ranking.append(currentCollageRank)
				if len(ranking) > 0:
					maxRank = min(ranking)
					if j != chefsRank:
						collegeRank[collegeRank.index(maxRank)] = -1
			j = j + 1
		if maxRank == -1 or maxRank == 0:
			print('0')
		else:
			print(collegeRank.index(maxRank) + 1)
	t = t - 1