#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 107;

double t[N][N], dis[N][N];

bool use[N];

inline void work() {
    int n, m;
    cin >> n >> m;
    vector<string> nam; nam.eb("");
    map<string, int> id;
    vector<pii> cor(n + 1);
    vector<int> fires;
    rep(i, 1, n) {
        string str; cin >> str;
        id[str] = i;
        nam.eb(str);
        use[i] = false;
        int x, y; cin >> x >> y;
        cor[i] = {x, y};
    }
    rep(i, 1, n) rep(j, 1, n) {
        t[i][j] = (i == j ? 0 : 1e18);
        auto [x1, y1] = cor[i];
        auto [x2, y2] = cor[j];
        dis[i][j] = sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
    }
    rep(i, 1, m) {
        string str; cin >> str; while (str == "") cin >> str;
        int a = id[str];
        cin >> str; cin >> str;
        int b = id[str];
        cin >> str; cin >> str; cin >> str;
        int c = id[str];
        double dif = (dis[c][a] - dis[b][a]) / 340;
        t[c][b] = min(t[c][b], dif);
        fires.eb(b);
        fires.eb(c);
    }
    sort(all(fires));
    fires.erase(unique(all(fires)), fires.end());
    rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) t[i][j] = min(t[i][j], t[i][k] + t[k][j]);
    rep(i, 1, n) if (t[i][i] < 0) {cout << "IMPOSSIBLE" << endl; return;}
    vector<string> ans;
    rep(turn, 1, fires.size()) {
        int id = 0;
        for (auto j : fires) if (!use[j]) {
            bool fl = true;
            for (auto k : fires)
                if (!use[k] && k != j && t[k][j] > 0) {fl = false; break;}
            if (fl) {id = j; break;}
        }
        if (id) {ans.eb(nam[id]); use[id] = true;}
        else {cout << "UNKNOWN" << endl; return;}
    }
    for (auto x : ans) cout << x << " ";
    cout << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) work();
    return 0;
}