big-p-and-punishment-5

Big P has become a Physical Education teacher at Hack International School.

Today, the students of class XII have been very undisciplined and he decides to punish them all.

He makes all of the N student (numbered 1 to N ) to stand in a line and asks them to sit down on their knees.

Students know that Big P is a very cruel and sadistic person and students start to sit down themselves when they see a friend sit down.

However, there are always some students who do not follow the trend. Now when Big P sees that happen , he slaps that student and makes him sit down. The same process as above is followed and is stopped when any - one student in the line refuses to sit down by himself.  

Given the students that Big P slaps to make them sit down , you need to tell the total no. of students who sat down in that line.

Note:  It is not necessary that if A is friend of B then B is also friend of A.

Input Format :
First Line Contains an integer T denoting no of test cases. 
Each test case begins with a line containing three integers N, F, S where N is the number of students in the line.         Next F lines have two integers A and B denoting the friendship between the students A and B.   Next S lines have one integer X denoting the student that was slapped by Big P .  

Output Format:
For each test case, output a line containing one integer, the total number of students that sit down in that line.

 T ≤ 10 , N ,F , S ≤ 10000 

SAMPLE INPUT
1
3 2 1
1 2
2 3
2

SAMPLE OUTPUT
2

Source: hackerearth | Difficulty: EASY


Solutions:
# problem 2

def color_it(frndsip_map,studentlist,i,visitlist):
	if len(frndsip_map[i])>0 :
		for j in frndsip_map[i] :
			if not visitlist[j]:
				studentlist[j-1]=True
				visitlist[j]=True
				color_it(frndsip_map,studentlist,j,visitlist)

def solve(frndsip_map,slappedlist,studentlist,visitlist):
	for i in slappedlist :
		studentlist[i-1]=True
		color_it(frndsip_map,studentlist,i,visitlist)
			

if __name__=="__main__" :
	T=int(input())

	for i in range(T):
		val=input().split()
		N=int(val[0])
		F=int(val[1])
		S=int(val[2])
		frndsip_map={}
		studentlist=[]
		visitlist={}
		for i in range(N):
			studentlist.append(False)
			frndsip_map[i+1]=[]
			visitlist[i+1]=False

		#print studentlist
		#print frndsip_map

		for i in range(F):
			f=input().split()
			frndsip_map[int(f[0])].append(int(f[1]))

		slappedlist=[]
		for i in range(S):
			x=int(input())
			slappedlist.append(x)
			visitlist[x]=True

		#print frndsip_map
		solve(frndsip_map,slappedlist,studentlist,visitlist)
		count=0
		for k in studentlist:
			if k :
				count +=1
		print(count)
		
		
		


def color_it(friendship_map,student_list,i,visitlist):
	if len(friendship_map[i])>0 :
		for j in friendship_map[i] :
			if not visitlist[j]:
				student_list[j-1]=True
				visitlist[j]=True
				color_it(friendship_map,student_list,j,visitlist)

def solve(friendship_map,slappedlist,student_list,visitlist):
	for i in slappedlist :
		student_list[i-1]=True
		color_it(friendship_map,student_list,i,visitlist)
			

if __name__=="__main__" :
	T=int(input())

	for i in range(T):
		val=input().split()
		N=int(val[0])
		F=int(val[1])
		S=int(val[2])
		friendship_map={}
		student_list=[]
		visitlist={}
		for i in range(N):
			student_list.append(False)
			friendship_map[i+1]=[]
			visitlist[i+1]=False

		for i in range(F):
			f=input().split()
			friendship_map[int(f[0])].append(int(f[1]))

		slappedlist=[]
		for i in range(S):
			x=int(input())
			slappedlist.append(x)
			visitlist[x]=True

		solve(friendship_map,slappedlist,student_list,visitlist)
		count=0
		for k in student_list:
			if k :
				count +=1
		print(count)