ITAI Virus (acm15_itai)


Time limit:
1000 ms
Memory limit:
64 MB

“Insane Transferable Abnormal Illness” or ITAI for short, is a new viral disease first discovered in a southern part of some city. The symptom is that persons contract with virus will continuously and uncontrollably scream “Itai, itai!”

When this virus was discovered at any city, it will perform binary division and spread through all roads connected to initial city. (The original city will have virus even though it has spread). But the ITAI virus is quite weak; after it has travelled to another city it will degenerate into “weak virus” that cannot spread anymore.

In a country, there is total of N cities, numbered from 1 to N, and has M road. The Ministry of Health has conducted an inspection and found this virus in K cities (All are new virus that can still spread)

To find out how many cities have virus after all virus has finished spreading.

Input

First line has number of question: T (1 ⩽ T ⩽ 10)

For question i (1 ⩽ i ⩽ T)

First line of question #i has three integer, N (number of city) M (number of road) and K (number that has virus) (1 ⩽ N ⩽ 1000; 1 ⩽ M ⩽ 2N; 0 ⩽ K ⩽ N)

Next M lines of question #i has integer A and B, represent the road connecting city A to city B.

Next line has K integers, each one is the initial cities found to have cirus.

Output

Has T lines, each line have the total number of city that has virus for question #i.

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None