###### 编程介的小学生

2017-06-20 15:28 阅读 681

# Water channels

Problem 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

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享