Water channels

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2229
64-bit integer IO format: %I64d      Java class name: Main

Description

So many towns are in drought! The mayor is anxious!
Luckily, There is a reservoir on the mountain top, and the mayor wants to use the water there to irrigate the farmland. The only way is to build some NEW channels to connect the towns that in drought to the reservoir directly or indirectly. Now the problem is the mayor wants to konw what is the least number of channels that have to build to connect all the towns in drought to the reservoir directly or indirectly.

Input

The input consists of multiple test cases. Each case begins with a line containing a positive integer n(0 <= n <= 100), following n pairs of towns in the form "A B", means there has been a channel from A to B. The third line contains a positive integer m(0 <= m <= 16), following m lines containing the names of those towns in drought. The last line contains a town's name which the reservoir is in. You should note that the names of the towns only contain 'A' to 'Z',and their length will less than 100.

Output

For each test case, output one line containing the minimum number of channels you have to built.

Sample Input

2
A B
B C
2
B
C
A
1
A B
2
B
C
A

Sample Output

0
1
Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .