N
S_1
S_2
...
S_N
M
A_1 B_1
A_2 B_2
...
A_M B_M
C
D

• 1 行目には崖および柱の総数 N (3 ≦ N ≦ 8) が与えられる。
• 2 行目からの N 行のうち i 行目には i 番目の崖または柱の名前 S_i が与えられる。
• S_i は大文字英アルファベットからなる。
• S_i の長さ |S_i| は 1 ≦ |S_i| ≦ 20 を満たす。
• i ≠ j のとき S_i ≠ S_j が保証される。
• N + 2 行目には崖や柱の間にかかっている氷の橋の本数 M (3 ≦ M ≦ N (N - 1) / 2) が与えられる。
• N + 3 行目からの M 行のうち i 行目には i 番目の氷の橋の両端の崖または柱の名前 A_i、 B_i が与えられる。
• ある氷の橋の両端が同一の崖または柱に接続されることがないことが保証される。
• 複数の氷の橋が同一の崖または柱のペアにかかることがないことが保証される。
• N + M + 3 行目には勇者一行が立っている崖の名前 C が与えられる。
• N + M + 4 行目には聖剣が安置されている崖の名前 D が与えられる。
• C ≠ D が保証される。
• 入力中では崖と柱が同一視される点に注意せよ。