Problem D

Pipelines

Problem

A company that builds gas pipelines has a project to refit a pipeline at a given site. The problem in question has several constraints that restrict the possibility of connecting sites. Given the prohibitive cost of installing new pipelines, the engineers wish to link two given sites by building the least number of connections possible.

The connections are obviously one way and are given by the source and destination sites. From the candidate connections, the goal is to build as few connections as possible to link the two sites.

Input

The input may have one or more cases. Each case is defined by:

1. The existing connections, given by a number of lines where each line holds the origin and destination sites
2. A blank line
3. A list of candidate connections, given in the same format as above
4. A blank line
5. The origin and destination sites that must be connected by a path

Each location name may be up to 30 characters long and may not hold whitespace.

Output

For each case, print a line with the number of connections necessary or the string No solution.

Sample Input

A B
D E

B C
A D
C D

A E
a b
b c
e f
h i

c e
c f
b d
d g
g i
e h
f h

a i
x y

y z
v w
w z

x w

Sample Output

1
2
No solution