Spider Jin

Time Limit : 1 sec, Memory Limit : 65536 KB

Spider Jin

正義のヒーロー「スパイダー人(スパイダージン)」は、腕からロープを出してビルからビルへ飛び移 ることができます。しかし、ロープが短いので自分からの距離が50以下のビルにしか移動できません。 それより遠くのビルに移動するには、一旦別のビルに飛び移らなくてはなりません。




ビルの数n、及びn個のビルの情報、スパイダー人の移動開始位置及び目的地を入力とし、その移動の最 短経路を出力して終了するプログラムを作成してください。 どのようにビルを経由しても目標のビルに移動できない場合はNAと出力してください。 各ビルは点として扱い、最短距離で移動するビルの経由方法が2つ以上存在することはないものとしま す。 入力として与えられる整数はすべて1以上1,000以下の値とします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下のとおりです。

1行目 ビルの数n(整数)
2行目 第1のビル情報 b1 x1 y1(それぞれ整数;半角空白区切り)
b1:ビル番号
x1:ビルのx座標
y1:ビルのy座標
3行目 第2のビル情報 b2 x2 y2(それぞれ整数;半角空白区切り)
:
n+1行目 第nのビル情報 bn xn yn(それぞれ整数;半角空白区切り)
n+2行目 移動情報の個数m(整数)
n+3行目 第1 の移動情報 s1 g1(それぞれ整数;半角空白区切り)
s1 スパイダー人の移動開始ビル番号
g1 スパイダー人の目的地ビル番号
n+4行目 第2 の移動情報 s2 g2(それぞれ整数;半角空白区切り)
:
n+m+2行目 第m の移動情報 sm gm(それぞれ整数;半角空白区切り)

Output

入力データセットごとに次の形式で出力します。

1行目 第1の移動情報に対する経路 s1 br11 br12・・・g1(それぞれ整数;半角空白区切り)または
NA
s1:スパイダー人の移動開始ビル番号
br11:第1の経由ビル
br12:第2の経由ビル
:
g1:スパイダー人の目的地ビル番号
2行目 第2の移動情報に対する経路 s2 br21 br22・・・g2(それぞれ整数;半角空白区切り)または
NA
:
m行目 第mの移動情報に対する経路 sm brm1 brm2・・・gm(それぞれ整数;半角空白区切り)または
NA

Sample Input

4
1 0 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0

Output for the Sample Input

1 2 3
NA
1 3 9 20 11 6 22

Source: PC Koshien 2007, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2007
http://www.pref.fukushima.jp/pc-concours/