vasya-and-party

Today is Vasya's birthday. On this special occasion, he has organized a party for all of his friends. These friends are enumerated by integers from 1 to N. Each of Vasya's friends has a Knowledge Level. In addition, each of them knows an arbitrary number of other people at the party. This friendship is bidirectional and transitive in nature, i.e if person A knows person B and person B knows person C, then we consider that person A knows person C. All these people who know each other come together and form a single group of friends.  

Now, they decide to play a game. In this game, among all groups of friends, the one with the highest knowledge level within each group is elected to represent the group during the game. Let's call this person the leader of the group.  If there are multiple candidates to be the leader of a group, you can select any of them arbitrarily. The game is then played after selecting these leaders.

Now, Vasya wants to find the number of distinct ways the game can be played. He finds this task too hard and wants you to help him. As this number can be large, print it Modulo 10^9+7.   

Input Format:

The first line contains two integers N and M denoting the number of people Vasya has invited to the party and the number of relations between these people. The next line contains N space separated integers denoting the where the i^{th} integer denotes the knowledge level of person i. Each of the next M lines contains 2 space separated integers u and v denoting that person u knows person v and vice-versa.  

Output Format

Print the required answer on a single line. As the answer may be large, print it Modulo 10^9+7 

Constraints

 1 ≤ N ≤ 10^5 

 0 ≤ M ≤ 10^5 

 0 ≤ A[i] ≤ 10^9  

 1 ≤ u,v ≤ N   

 M ≤ (N*(N-1))/2     

Note:

There can be self loops, i.e edges from and to the same person and multple edges from one person to another. 

SAMPLE INPUT
5 4
1 2 3 4 5
1 2
2 3
3 4
4 5

SAMPLE OUTPUT
1

Explanation

Here, all the people at the party know each other. Among this group the person with the highest knowledge is person 5. Hence, there is only one way.

Source: hackerearth | Difficulty: EASY
Tags: Graph algorithms

Data structures

Graph traversal


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
N, M = list(map(int, input().strip().split()))
A = list(map(int, input().strip().split()))
adj_list = [[] for i in range(N)]
for edge in range(M):
	i, j = list(map(int, input().strip().split()))
	if i == j:
		continue
	adj_list[i-1].append(j-1)
	adj_list[j-1].append(i-1)
 
components = []	
visited = [False for i in range(N)]
 
for i in range(N):
	if visited[i] == False:
		component = []
		dfs_stack = [i]
		comp_max = 0
		while dfs_stack:
			elem = dfs_stack.pop()
			if visited[elem] == False:
				visited[elem] = True
				component.append(A[elem])
				if comp_max < A[elem]:
					comp_max = A[elem]
			for child in adj_list[elem]:
				if not visited[child]:
					dfs_stack.append(child)
		comp_max_count = component.count(comp_max)			
		if comp_max_count > 1:
			components.append(comp_max_count)			
 
 
mod_num = 1000000007
count_pro = 1
for count in components:	
	count_pro *=count
	count_pro %= mod_num
print(count_pro	% mod_num)


from functools import reduce
def getRoots(aNeigh):
	def findRoot(aNode,aRoot):
		while aNode != aRoot[aNode][0]:
			aNode = aRoot[aNode][0]
		return (aNode,aRoot[aNode][1])
	myRoot = {} 
	for myNode in list(aNeigh.keys()):
		myRoot[myNode] = (myNode,0)  
	for myI in aNeigh: 
		for myJ in aNeigh[myI]: 
			(myRoot_myI,myDepthMyI) = findRoot(myI,myRoot) 
			(myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot) 
			if myRoot_myI != myRoot_myJ: 
				myMin = myRoot_myI
				myMax = myRoot_myJ 
				if  myDepthMyI > myDepthMyJ: 
					myMin = myRoot_myJ
					myMax = myRoot_myI
				myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))
				myRoot[myMin] = (myRoot[myMax][0],-1) 
	myToRet = {}
	for myI in aNeigh: 
		if myRoot[myI][0] == myI:
			myToRet[myI] = []
	for myI in aNeigh: 
		myToRet[findRoot(myI,myRoot)[0]].append(myI) 
	return myToRet  




nodes,total_edges=tuple(map(int, input().split()))

array_knowledge=list(map(int, input().split()))
#print nodes

keys=list(range(1,nodes+1))
#print keys
mydict=dict(list(zip(keys, [[]]*len(keys))))

#print mydict

temp=total_edges
while temp>0:
	u,v=list(map(int, input().split()))
	mydict[u]=mydict[u]+[v]
	mydict[v]=mydict[v]+[u]	
	temp=temp-1
#print mydict
#print getRoots(mydict)
#print len(getRoots(mydict).keys())
num_ways_list=[]
for i in getRoots(mydict).values():
	temp_list=[]
	for j in i:
		temp_list.append(array_knowledge[j-1])
#    print temp_list		
	max_knowledge=max(temp_list)
	num_ways_list.append(temp_list.count(max_knowledge))
#print num_ways_list 
result=reduce(lambda x,y: x*y, num_ways_list)
print(result%(1000000007)) 


def getRoots(aNeigh):
	def findRoot(aNode,aRoot):
		while aNode != aRoot[aNode][0]:
			aNode = aRoot[aNode][0]
		return (aNode,aRoot[aNode][1])
	myRoot = {} 
	for myNode in list(aNeigh.keys()):
		myRoot[myNode] = (myNode,0)  
	for myI in aNeigh: 
		for myJ in aNeigh[myI]: 
			(myRoot_myI,myDepthMyI) = findRoot(myI,myRoot) 
			(myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot) 
			if myRoot_myI != myRoot_myJ: 
				myMin = myRoot_myI
				myMax = myRoot_myJ 
				if  myDepthMyI > myDepthMyJ: 
					myMin = myRoot_myJ
					myMax = myRoot_myI
				myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))
				myRoot[myMin] = (myRoot[myMax][0],-1) 
	myToRet = {}
	for myI in aNeigh: 
		if myRoot[myI][0] == myI:
			myToRet[myI] = []
	for myI in aNeigh: 
		myToRet[findRoot(myI,myRoot)[0]].append(myI) 
	return myToRet

#myGraph = {0: [1,2,3], 1: [0,1], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []}
#print getRoots(myGraph)
n,m=list(map(int,input().strip().split()))
knwl=list(map(int,input().strip().split()))

myGraph={}
while m>0:
	a,b=list(map(int,input().strip().split()))
	if a not in myGraph:
		myGraph[a]=[b]
	myGraph[a].append(b)
	if b not in myGraph:
		myGraph[b]=[a]
	myGraph[b].append(a)
	m=m-1
comp=getRoots(myGraph)
res=1
for i in comp:
	l=[]
	for j in comp[i]:
		l.append(knwl[j-1])
	mx=max(l)
	res=(res*(l.count(mx)))%1000000007
print(res%1000000007)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
A=input("").split(" ")
people=(int)(A[0])
n_bond=(int)(A[1])
knowledge=input("").split(" ")
dp={}
playing={}
ans=1

for i in range(people):
	dp.setdefault(i+1,set([]))
	playing.setdefault(i+1,0)

for i in range(n_bond):
	con=input("").split(" ")
	a=(int)(con[0])
	b=(int)(con[1])
	dp[a].add(b)
	dp[b].add(a)

def dfs(person,network,knowledge,playing):
	visited,stack=set(),[person]
	while stack:
		vertex=stack.pop()
		if vertex not in visited:
			visited.add(vertex)
			stack.extend(network[vertex]-visited)
	max=-sys.maxsize

	count=0
	obj_count={}
	if len(visited) ==1:
		playing[visited.pop()]=1
		return 1
	for i in range(len(visited)):
		poop=visited.pop()
		playing[poop]=1
		value=(int)(knowledge[poop-1])
		if max < value:
			max=value
		if value not in obj_count:
			obj_count.setdefault(value,1)
		else:
			obj_count[value]+=1
	return obj_count[max]			
	
for i in range(people):
	if playing[i+1]==0:
		n_ways=dfs(i+1,dp,knowledge,playing)
		ans*=n_ways
		ans=ans%(10**9+7)

print(ans%(10**9+7))


n,m=list(map(int,input().split()))
k=list(map(int,input().split()))
rel=[[] for x in range(n+1)]
mod=10**9+7
flag=[False]*(n+1)
flag[0]=True

grps=[]
while m>0:
	u,v=list(map(int,input().split()))
	rel[u].append(v)
	rel[v].append(u)
	m-=1
# for x in range(len(rel)):
#     print x,rel[x]
gi=0
pi=1
rn=list(range(1,n))
for x in rn:
	if not flag[x]:
		tp=rel[x]
		grp=set(tp)
		grp.add(x)
		while tp:
			tmp=tp.pop()
			grp.add(tmp)
			if not flag[tmp]:
				flag[tmp]=True
				tp.extend(rel[tmp])
		grps.append(grp)
		#print grp
res=1
for grp in grps:
	kl=[k[x-1] for x in grp]
	res=res*kl.count(max(kl))%mod
print(res)


n, m = input().split()
people = input().split() # don't need to convert to int
CONST = 10**9 + 7

# each element equals a connected component
# and each element of component is people
groups = []
# and each element of component is group_index
groups_i = []

group_index = -1

# each element corresponds to the group its index is in.
group_nums = [group_index]*int(n)

for _ in range(int(m)):
	uv = input().split()
	u = int(uv[0]) - 1
	v = int(uv[1]) - 1

	# if none of them are in a group, create a new group
	# and let them in
	if group_nums[u] == -1 and group_nums[v] == -1:
		group_index += 1
		# to avoid counting self loops
		if u == v:
			groups.append([people[u]])
			groups_i.append([u])
			group_nums[u] = group_index
		else:
			group_nums[u] = group_index
			group_nums[v] = group_index
			groups.append([people[u], people[v]])
			groups_i.append([u, v])
	elif group_nums[u] != -1 and group_nums[v] != -1:
		# to avoid counting duplicate relations or 2-node loops
		if group_nums[u] != group_nums[v]:
			if len(groups[group_nums[u]]) >= len(groups[group_nums[v]]):
				tv = v
				tu = u
			else:
				tv = u
				tu = v
			temp = group_nums[tv]
			for index in groups_i[temp]:
				group_nums[index] = group_nums[tu]
			groups[group_nums[tu]].extend(groups[temp])
			groups_i[group_nums[tu]].extend(groups_i[temp])
			del groups[temp][:]
			del groups_i[temp][:]
			
	# if one of them is in a group, put the other in the same group
	elif group_nums[u] != -1:
		# to avoid counting self loops
		if u != v:
			group_nums[v] = group_nums[u]
			groups[group_nums[u]].append(people[v])
			groups_i[group_nums[u]].append(v)
	elif group_nums[v] != -1:
		# to avoid counting self loops
		if u != v:
			group_nums[u] = group_nums[v]
			groups[group_nums[v]].append(people[u])
			groups_i[group_nums[v]].append(u)

del group_nums[:]
del people[:]
del groups_i[:]



prod = 1
for group in groups:
	if not group:
		continue
	m = max(group)
	prod = ((prod % CONST) * (group.count(m) % CONST) ) % CONST
print(prod)


def getRoots(aNeigh):
	def findRoot(aNode,aRoot):
		while aNode != aRoot[aNode][0]:
			aNode = aRoot[aNode][0]
		return (aNode,aRoot[aNode][1])
	myRoot = {} 
	for myNode in list(aNeigh.keys()):
		myRoot[myNode] = (myNode,0)  
	for myI in aNeigh: 
		for myJ in aNeigh[myI]: 
			(myRoot_myI,myDepthMyI) = findRoot(myI,myRoot) 
			(myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot) 
			if myRoot_myI != myRoot_myJ: 
				myMin = myRoot_myI
				myMax = myRoot_myJ 
				if  myDepthMyI > myDepthMyJ: 
					myMin = myRoot_myJ
					myMax = myRoot_myI
				myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))
				myRoot[myMin] = (myRoot[myMax][0],-1) 
	myToRet = {}
	for myI in aNeigh: 
		if myRoot[myI][0] == myI:
			myToRet[myI] = []
	for myI in aNeigh: 
		myToRet[findRoot(myI,myRoot)[0]].append(myI) 
	return myToRet

#myGraph = {0: [1,2,3], 1: [0,1], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []}
#print getRoots(myGraph)
n,m=list(map(int,input().strip().split()))
knwl=list(map(int,input().strip().split()))

myGraph={}
while m>0:
	a,b=list(map(int,input().strip().split()))
	if a not in myGraph:
		myGraph[a]=[b]
	myGraph[a].append(b)
	if b not in myGraph:
		myGraph[b]=[a]
	myGraph[b].append(a)
	m=m-1
comp=getRoots(myGraph)
res=1
for i in comp:
	l=[]
	for j in comp[i]:
		l.append(knwl[j-1])
	mx=max(l)
	res=(res*(l.count(mx)))%1000000007
print(res%1000000007)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
A=input("").split(" ")
people=(int)(A[0])
n_bond=(int)(A[1])
knowledge=input("").split(" ")
dp={}
playing={}
ans=1

for i in range(people):
	dp.setdefault(i+1,set([]))
	playing.setdefault(i+1,0)

for i in range(n_bond):
	con=input("").split(" ")
	a=(int)(con[0])
	b=(int)(con[1])
	dp[a].add(b)
	dp[b].add(a)

def dfs(person,network,knowledge,playing):
	visited,stack=set(),[person]
	while stack:
		vertex=stack.pop()
		if vertex not in visited:
			visited.add(vertex)
			stack.extend(network[vertex]-visited)
	max=-sys.maxsize

	count=0
	obj_count={}
	if len(visited) ==1:
		playing[visited.pop()]=1
		return 1
	for i in range(len(visited)):
		poop=visited.pop()
		playing[poop]=1
		value=(int)(knowledge[poop-1])
		if max < value:
			max=value
		if value not in obj_count:
			obj_count.setdefault(value,1)
		else:
			obj_count[value]+=1
	return obj_count[max]			
	
for i in range(people):
	if playing[i+1]==0:
		n_ways=dfs(i+1,dp,knowledge,playing)
		ans*=n_ways
		ans=ans%(10**9+7)

print(ans%(10**9+7))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
N, M = list(map(int, input().strip().split()))
A = list(map(int, input().strip().split()))
adj_list = [[] for i in range(N)]
for edge in range(M):
	i, j = list(map(int, input().strip().split()))
	if i == j:
		continue
	adj_list[i-1].append(j-1)
	adj_list[j-1].append(i-1)

components = []	
visited = [False for i in range(N)]

for i in range(N):
	if visited[i] == False:
		component = []
		dfs_stack = [i]
		comp_max = 0
		while dfs_stack:
			elem = dfs_stack.pop()
			if visited[elem] == False:
				visited[elem] = True
				component.append(A[elem])
				if comp_max < A[elem]:
					comp_max = A[elem]
			for child in adj_list[elem]:
				if not visited[child]:
					dfs_stack.append(child)
		comp_max_count = component.count(comp_max)			
		if comp_max_count > 1:
			components.append(comp_max_count)			


mod_num = 1000000007
count_pro = 1
for count in components:	
	count_pro *=count
	count_pro %= mod_num
print(count_pro	% mod_num)
				
			
		
		



from collections import deque
mod = 10**9 + 7
edgeHistory = set()
N, G, ANS, V, K = 0, [], [], [], []


def bfs(i, node):
	global G, V, K, ANS
	q = deque()
	q.append(i)
	while q:
		# print '\nq: ', q, ' MAX: ', ANS[node][0], ' c: ', ANS[node][1]
		val = q.popleft()
		if V[val] != 1:
			V[val] = 1
			if K[val] == ANS[node][0] and val != node:
				ANS[node][1] += 1

			elif K[val] > ANS[node][0]:
				ANS[node][1] = 1
				ANS[node][0] = K[val]

			for adj in G[val]:
				if not V[adj]:
					q.append(adj)


def solve():
	global V, ANS, K, N, G
	# assert len(G) == N + 1 and len(ANS) == N + 1
	# Solves the given graph using DFS
	ways = 1
	V = [0] * (N + 1)
	ANS = [[K[i], 1] for i in range(N + 1)]

	for i in range(1, N + 1):
		if not V[i]:
			bfs(i, i)
	for i in range(N + 1):
		ways = (ways * ANS[i][1]) % mod
	return ways

if __name__ == '__main__':
	N, M = list(map(int, input().split()))
	K = [0] + list(map(int, input().split()))
	G = [[] for i in range(N + 1)]

	ways = 1
	for _ in range(M):
		# there can be multiple and self loops
		u, v = list(map(int, input().split()))
		# saved from self edges
		if u == v:
			continue
		if tuple(sorted([u, v])) in edgeHistory:
			continue
		else:
			edgeHistory.add(tuple(sorted([u, v])))
		G[u].append(v)
		G[v].append(u)

	# print G
	print(solve())


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
A=input("").split(" ")
people=(int)(A[0])
n_bond=(int)(A[1])
knowledge=input("").split(" ")
dp={}
playing={}
ans=1

for i in range(people):
	dp.setdefault(i+1,set([]))
	playing.setdefault(i+1,0)

for i in range(n_bond):
	con=input("").split(" ")
	a=(int)(con[0])
	b=(int)(con[1])
	dp[a].add(b)
	dp[b].add(a)

def dfs(person,network,knowledge,playing):
	visited,stack=set(),[person]
	while stack:
		vertex=stack.pop()
		if vertex not in visited:
			visited.add(vertex)
			stack.extend(network[vertex]-visited)
	max=-sys.maxsize

	count=0
	obj_count={}
	if len(visited) ==1:
		playing[visited.pop()]=1
		return 1
	for i in range(len(visited)):
		poop=visited.pop()
		playing[poop]=1
		value=(int)(knowledge[poop-1])
		if max < value:
			max=value
		if value not in obj_count:
			obj_count.setdefault(value,1)
		else:
			obj_count[value]+=1
	return obj_count[max]			
	
for i in range(people):
	if playing[i+1]==0:
		n_ways=dfs(i+1,dp,knowledge,playing)
		ans*=n_ways
		ans=ans%(10**9+7)

print(ans%(10**9+7))