Traffic Engineering

Time limit1sMemory limit256 MB

Summary

Given a directed network of named hosts where nodes cost 0 or 1 depending on ownership, report the cheapest route cost between each source-destination pair.

Level: Medium5 of 10
Topics: Graph, Shortest path, Heap, Implementation
Solved: No attempts yet

Problem

ISPs live on very thin margins, so choosing the cheapest route for network traffic matters for the company's survival. For the person sending the data, find the cheapest route between two hosts on the Internet.

Each node (host) has a cost:

Passing through a node owned by the sender is essentially free and costs $0.
Passing through a node owned by someone else costs $1 per node.

The cost of a route is the sum of the costs of every node on that route, and both the source and the destination nodes count toward the cost. Among all routes that follow the directed links from the source to the destination, report the minimum possible cost.

Input

The input consists of several networks. Each network is given in the following order:

One integer giving the number of network links that follow.
That many network links. Each link is a pair of names describing a one-way (directed) connection from the first name to the second name.
One integer giving the number of nodes owned by the sender, followed by that many owned node names.
One integer giving the number of (source, destination) pairs to route between, followed by that many pairs of nodes; in each pair the source comes first and the destination second.

A network whose link count is 0 marks the end of the input and must not be processed. A single network has at most 100 nodes.

Output

For each (source, destination) pair, print on its own line a single integer giving the minimum cost of sending that packet. An owned node costs 0 and a non-owned node costs 1. The source and destination nodes both count toward the cost. Print the results for every query of every network in the order they appear in the input.

Examples5

Example 1

Input

5
Alice Bob
Bob Charlie
Alice Charlie
Charlie Dave
Dave Alice
2
Alice
Bob
2
Alice Bob
Bob Alice
0

Expected output

0
2

Example 2
Input
```
1
A B
1
A
1
A A
0
```
Expected output
```
0
```
Example 3
Input
```
1
A B
0
1
B B
0
```
Expected output
```
1
```
Example 4
Input
```
1
A B
1
A
1
A B
0
```
Expected output
```
1
```
Example 5
Input
```
4
S X
X T
S Y
Y T
1
X
1
S T
0
```
Expected output
```
2
```