#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

    double d[1000][1000];

int main() {

  const double l_max = 1000000.00;

  while( true ) {

    long long int n;
    cin >> n;
    if ( n == 0 ) break;

    long long int x[1000], y[1000];
    for ( long long int i = 0; i < n; i++ ) {

      long long int b;
      cin >> b;
      b--;
      cin >> x[b] >> y[b];

    }

    for ( long long int i = 0; i < n; i++ ) {
      for ( long long int j = 0; j < n; j++ ) {
	long long int dx = x[i] - x[j];
	long long int dy = y[i] - y[j];
	dx *= dx;
	dy *= dy;
	if ( i == j || dx + dy > 2500 ) {
	  d[i][j] = l_max;
	}else {
	  d[i][j] = sqrt( dx + dy );
	}
      }
    }

    long long int m;
    cin >> m;
    for ( long long int m2 = 0; m2 < m; m2++ ) {

      long long int st, go;
      cin >> st >> go;
      st--;
      go--;

      bool flag[1000] = {};
      double s[1000] = {0.00};
      for ( long long int i = 0; i < n; i++ ) {
	s[i] = l_max;
      }
      s[st] = 0.00;
      long long int b[1000];
      b[go] = -1;

      while( true ) {

	long long int ne = -1;
	for ( long long int i = 0; i < n; i++ ) {
	  if ( flag[i] == false && ( ne == -1 || s[i] < s[ne] ) ) {
	    ne = i;
	  }
	}
	if ( ne == -1 ) break;
	flag[ne] = true;

	for ( long long int i = 0; i < n; i++ ) {
	  if ( s[i] > s[ne] + d[ne][i] ) {
	    s[i] = s[ne] + d[ne][i];
	    b[i] = ne;
	  }
	}

      }

      if ( b[go] == -1 ) {
	cout << "NA" << endl;
	continue;
      }

      vector< long long int > ans;

      long long int k = go;
      while( k != st ) {
	k = b[k];
	ans.push_back(k);
      }

      for ( long long int i = 0; i < ans.size(); i++ ) {
	cout << ans[ ans.size() - 1 - i ] + 1 << " ";
      }
      cout << go + 1 << endl;

    }

  }

  return 0;

}