Problem L: WW

Problem

19XX年、nつの国で連合国軍が結成された。連合国軍に属する各国では、敵軍の侵略から自国を守るために国内に１つ以上の拠点を作り、周囲を警戒している。図１は連合国の例を示し、長方形が各国を、その中にある円がその国の拠点を表す。

図1

敵軍が侵略してきた場合、それを一番最初に発見した拠点からその情報を連合国軍に属する他国または自国の拠点に発信することになっている。 情報を他の拠点に伝えるには正の整数のコストがかかる。

また、各国では自国の拠点のうち、連合国軍翻訳通信部(ATIS : Allied Translator and Interpreter Section)に属する兵士が配属されている拠点をちょうど１つだけ持っている。 この兵士だけが連合国軍に属する全ての国の言語を話すことができ、その他の兵士は自分の国の言語しか話せない。 その為、情報を受け取った拠点が他国に情報を伝えようとした際にその拠点がATISに属する兵士をもたない場合、そこから自国のATISに属する兵士をもつ拠点に情報を伝え他国に情報を発信してもらう必要がある。

国毎で各拠点に０から順に[その国がもつ拠点の数-1]までの番号が割り振られており、０番目の拠点にATISに属する兵士がいる。 つまり、他国の拠点に情報を伝達できるのは０番目の拠点だけであり、その他の拠点から他国へは通信できない。 また、その国の０番目の拠点に情報が伝わればその国全体に情報が伝わったものとする。

様々な理由から、全ての拠点の間で通信ができるとは限らない。 ある拠点から別の拠点に情報を伝える事ができたとしても、その逆が成り立つとは限らない。 また、ある拠点から別の拠点に情報を伝えた際のコストとその逆でかかるコストが同じとも限らない。

これらのことを踏まえて、ある拠点が敵軍を発見した際に、連合国軍全体に情報が行き渡るコストの総和が最も少ない伝達方法を知りたい。 連合国軍に属する全ての国の０番目の拠点に対して最初に敵軍を見つけた拠点から情報が伝達された時、連合国軍全体に情報が行き渡ったものとする。

敵軍を発見した拠点が質問として与えられるので、最も少ないコストでその情報が連合国軍全体に行き渡る伝達方法とそのコストを出力せよ。

例えば、以下のケースについて考える ( Sample Input 4、１つめの質問 )

国neepalの1番目の拠点が敵軍を発見したとする。 この場合、１番目の拠点から他国へは通信できないため、まず自国の０番目の拠点へ情報を伝える。

次に、０番目の拠点から国luxenbourg,nowayに情報を伝える。 neepalからluxenbourgの０番目の拠点へ直接通信することはできるが、３番目の拠点に情報を伝え、そこから０番目の拠点へ伝えたほうがコストが少なく済む。 この場合、全ての国の０番目の国へ情報を伝えるためにかかる最小のコストは１２となる。 コストが１２で済む伝達方法は複数存在するが、そのうちのどれか一つを答えとして出力すれば良い。

以下の図２の赤い矢印はその答えのうちの１つである。

図2

Input

n
countryname0 m0 
countryname1 m1
…
countrynamen-1 mn-1
e
c10 v10 c20 v20 cost0
c11 v11 c21 v21 cost1
…
c1e-1 v1e-1 c2e-1 v2e-1 coste-1
q 
c30 v30 
c31 v31 
…
c3q-1 v3q-1

• nは連合国軍に属する国の数を表す
• countryname_iは連合国軍に属するi番目の国名を,m_iはi番目の国の拠点の数を表す
• eは通信可能な拠点のペアの数を表す
• 続くe行には国c1_iの拠点v1_iから国c2_iの拠点v2_iに情報を伝えるのにかかるコストcost_iが与えられる
• qは質問の数を表す
• 続くq行には敵軍を発見した国の名前c3_iとその拠点v3_iが与えられる
• c1_i,c2_i,c3_iは連合国軍に属する国のいずれかである
• v1_i,v2_i,v3_iはその国の拠点の数以上である事は無い

Constraints

• 1 ≤ n ≤ 26
• 1 ≤ m_i ≤ 100
• 0 ≤ e ≤ 322400
• 0 ≤ cost_i ≤ 100
• 1 ≤ q ≤ 10
• countryname は小文字のアルファベット ‘a’ から’z’までで構成される長さ１以上２０以下の文字列である
• 同じ名前の国が2つ以上与えられる事はない
• 通信可能な拠点のペアのc1_iとc2_iが同じ時、v1_iとv2_iは異なる
• 通信可能な拠点のペアのc1_iとc2_iが異なる時、v1_iは必ず0である

Output

各質問に対して以下の形式で答えを出力する。

各質問に対する答えの最後の行には、５つの '-’ からなる"-----” ( “ は除く ) という1行を出力すること。

答えが存在する場合

1行目に質問で与えられた国の拠点から連合国軍全体に情報が行き渡るために必要なコストの最小値を出力する。

2行目以降にはその時の伝達方法を出力する。 伝達方法は以下の形式で表現される。

c40 v40 c50 v50 
c41 v41 c51 v51 
...

国c4_iの拠点v4_iから国c5_iの拠点v5_iに情報を伝えたことを表す。

以下の事に気をつける事。

• 通信が行われた順番通りに出力する必要はない
• コストの総和が最小となる伝達方法が1つ以上存在する場合、そのうちのいずれか１つを出力すれば良い
• 同じ通信可能なペアを２回以上出力してはいけない
• c4_i,c5_iは入力で与えられた国のいずれかでなければならない
• v4_i,v5_iはその国の拠点の数未満でなければならない

答えが存在しない場合

1行に ”Impossible” ( “ は除く ) と出力すること。

Sample Input 1

3
frence 1
usi 1
powland 1
2
usi 0 frence 0 10
frence 0 powland 0 10
2
usi 0
powland 0

Sample Output 1

20
usi 0 frence 0
frence 0 powland 0
-----
Impossible
-----

Sample Input 2

2
usso 2
caneda 2
4
usso 1 usso 0 1
usso 0 caneda 0 10
usso 0 caneda 1 2
caneda 1 caneda 0 2
1
usso 1

Sample Output 2

5
usso 1 usso 0
usso 0 caneda 1
caneda 1 caneda 0
-----

Sample Input 3

3
chinax 1
ok 1
austraria 2
6
chinax 0 austraria 0 5
austraria 0 chinax 0 5
austraria 1 austraria 0 1
ok 0 austraria 0 5
austraria 0 ok 0 5
ok 0 austraria 1 1
2
chinax 0
ok 0

Sample Output 3

10
chinax 0 austraria 0
austraria 0 ok 0
-----
7
ok 0 austraria 1
austraria 1 austraria 0
austraria 0 chinax 0
-----

Sample Input 4

3
neepal 2
luxenbourg 4
noway 2
12
neepal 1 neepal 0 2
neepal 0 noway 1 2
neepal 0 luxenbourg 0 10
neepal 0 luxenbourg 3 2
luxenbourg 3 luxenbourg 1 2
luxenbourg 3 luxenbourg 2 2
luxenbourg 1 luxenbourg 0 2
luxenbourg 2 luxenbourg 0 2
noway 1 noway 0 2
noway 0 neepal 0 2
noway 0 luxenbourg 3 2
noway 0 luxenbourg 0 10
3
neepal 1
luxenbourg 3
noway 1

Sample Output 4

12
neepal 1 neepal 0
neepal 0 luxenbourg 3
luxenbourg 3 luxenbourg 2
luxenbourg 2 luxenbourg 0
neepal 0 noway 1
noway 1 noway 0
-----
Impossible
-----
10
noway 1 noway 0
neepal 0 luxenbourg 3
luxenbourg 3 luxenbourg 2
luxenbourg 2 luxenbourg 0
noway 0 neepal 0
-----