Santa is still not married. He approaches a marriage bureau and asks them to hurry the process. The bureau checks the list of eligible girls of size N and hands it over to Santa. Santa being conscious about his marriage is determined to find a girl with maximum connections so that he can gather more information about her. Accordingly, he looks to figure out the maximum number of girls (from the list) who know each other to achieve the above purpose.
In order to finalize the girl, he needs to find the Kth prime. Where k = largest group of girls who know each other. Considering Santa's poor knowledge of Maths, he seeks Banta's help for the answer. Now you, a fan of Santa Banta Jokes, take this prestigious opportunity to solve the problem.
In case no of connections is zero, print "-1". Here the connection between girls is represented by a 2-D array g of dimension M*2, where M is the number of connections.
Note :
1. Suppose girl "a" knows girl "b" and girl "b" knows girl "c", then girl "a" also knows girl "c". Transitivity holds here.
2. Consider 1 as a composite number.
3. For precompute function given in the template you just have to complete it and use it wherever required, do not call it again and again, it is already being called by driver function before executing test cases. 
Example 1:
Input : 
N = 10
M = 6
g[] = {{1,2},{2,3},{3,4},{4,5},{6,7},{9,10}}
Output : 
11
Explanation:
Here in this graph there are 4 groups. 
In 1^{st} group: (1 -> 2 -> 3 -> 4 -> 5) are 
there. In 2^{nd} group: (6 -> 7) are there.
In 3^{rd }group: (8) is there.
In 4^{th} group: (10 -> 9) are there.
In these 4 group the maximum number of 
value is 5. So, K = 5 and the 5^{th} prime number 
is 11. Return 11.
Example 2:
Input : 
N = 2
M = 1
g[] = {{1, 2}} 
Output : 
3
Explanation:
In this Example there will only be a 
single group of 2 girls, and hence the 
value of K is 2, The 2nd prime is 3.
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function helpSanta() that takes a number of girls (n), a number of connections (m), a 2-D array of girls connections (g), and return the Kth prime no if there are no connections then return -1. The driver code takes care of the printing.
Expected Time Complexity: O(N + M).
Expected Auxiliary Space: O(N + M).
Constraints:
1 ≤ n ≤ 10^{5}
0 ≤ m ≤ 10^{5}
1 ≤ u, v ≤ n
Sum of n+m will not exceed 10^{5}.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def precompute(self):

        #Complete the function

    

    def helpSanta (self, n, m, g) : 

        #Complete the function



Solutions:
def precompute():
	pass

def helpSanta(n, m, g):
	if m == 0:
		return -1
	parent = list(range(n))
	rank = [1] * n

	def find(n):
		if parent[n] != n:
			parent[n] = find(parent[n])
		return parent[n]

	def union(a, b):
		(x, y) = (find(a), find(b))
		if x == y:
			return False
		if rank[x] > rank[y]:
			parent[y] = x
			rank[x] += rank[y]
		else:
			parent[x] = y
			rank[y] += rank[x]
		return True
	for i in range(m):
		(a, b) = g[i]
		union(a - 1, b - 1)
	maxi = max(rank)
	sz = maxi * 20
	sieve = [True] * (sz + 1)
	for i in range(2, sz + 1):
		if sieve[i]:
			for j in range(i * i, sz + 1, i):
				sieve[j] = False
			maxi -= 1
			if maxi == 0:
				return i


import sys
sys.setrecursionlimit(10000)

def precompute():
	pass

def prime(n):
	primes = []
	count = 0
	for j in range(2, 999999):
		fl = 0
		for i in range(2, int(j ** 0.5) + 1):
			if j % i == 0:
				fl = 1
				break
		if fl == 0:
			count += 1
			primes.append(j)
		if count == n:
			return primes[-1]

def helpSanta(n, m, g):
	if n == 0 or m == 0:
		return -1
	adj = {}
	for i in range(1, n + 1):
		adj[i] = []
	for k in g:
		(s, d) = k
		adj[s].append(d)
		adj[d].append(s)
	visited = [False for i in range(n + 1)]

	def dfs(v, adj):
		visited[v] = True
		q = [v]
		count = 1
		while q:
			curr = q.pop()
			for k in adj[curr]:
				if visited[k] == False:
					q.append(k)
					visited[k] = True
					count += 1
		return count
	mx = -99
	for i in range(1, n + 1):
		if visited[i] == False:
			mx = max(mx, dfs(i, adj))
	return prime(mx)
precompute()
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(m):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	ans = helpSanta(n, m, arr)
	print(ans)


import sys
sys.setrecursionlimit(10000)

def precompute():
	pass

def prime(n):
	primes = []
	count = 0
	for j in range(2, 999999):
		fl = 0
		for i in range(2, int(j ** 0.5) + 1):
			if j % i == 0:
				fl = 1
				break
		if fl == 0:
			count += 1
			primes.append(j)
		if count == n:
			return primes[-1]

def helpSanta(n, m, g):
	if n == 0 or m == 0:
		return -1
	adj = {}
	for i in range(1, n + 1):
		adj[i] = []
	for k in g:
		(s, d) = k
		adj[s].append(d)
		adj[d].append(s)
	visited = [False for i in range(n + 1)]

	def dfs(v, adj):
		visited[v] = True
		q = [v]
		count = 1
		while q:
			curr = q.pop()
			for k in adj[curr]:
				if visited[k] == False:
					q.append(k)
					visited[k] = True
					count += 1
		return count
	mx = -99
	for i in range(1, n + 1):
		if visited[i] == False:
			mx = max(mx, dfs(i, adj))
	return prime(mx)