#include int ri() { int n; scanf("%d", &n); return n; } template using pqueue_inv = std::priority_queue, std::greater >; const double DINF = 1000000000; int main() { int n = ri(); int m = ri(); int k = ri(); int x = ri() - 1, y = ri() - 1; std::pair pts[n]; for (auto &i : pts) i.first = ri(), i.second = ri(); auto calc_dist = [&] (int i, int j) { return std::hypot(pts[i].first - pts[j].first, pts[i].second - pts[j].second); }; std::vector > hen[n]; for (int i = 0; i < m; i++) { int x = ri() - 1; int y = ri() - 1; hen[x].push_back({y, calc_dist(x, y)}); hen[y].push_back({x, calc_dist(x, y)}); } struct Payload { double cur_cost; int pos; std::vector used; bool operator > (const Payload &rhs) const { return cur_cost > rhs.cur_cost; } bool operator < (const Payload &rhs) const { return cur_cost < rhs.cur_cost; } }; auto dijkstra = [&] (int s, int t, const std::vector &used) { std::vector dist(n, DINF); pqueue_inv > que; que.push({dist[s] = 0, s}); while (que.size()) { auto j = que.top(); que.pop(); if (j.first != dist[j.second]) continue; for (auto k : hen[j.second]) { if (used[k.first]) continue; if (dist[k.first] > j.first + k.second) que.push({dist[k.first] = j.first + k.second, k.first}); } } return dist[t]; }; if (dijkstra(x, y, std::vector(n)) == DINF) { for (int i = 0; i < k; i++) puts("-1"); return 0; } pqueue_inv > que; std::vector > all[n]; std::vector init_(n); init_[x] = true; que.push({dijkstra(x, y, std::vector(n)), {0, x, init_}}); while (que.size()) { auto i = que.top(); que.pop(); double cur_cost = i.second.cur_cost; int x = i.second.pos; auto &used = i.second.used; if ((int) all[x].size() >= k) continue; all[x].push_back(i); for (auto j : hen[x]) { if (used[j.first]) continue; used[j.first] = true; double cost = dijkstra(j.first, y, used); if (cost == DINF) continue; double new_estimated = cost + cur_cost + j.second; que.push({new_estimated, {cur_cost + j.second, j.first, used}}); // bfs used[j.first] = false; } } for (int i = 0; i < k; i++) { if (i < (int) all[y].size()) { printf("%.11f\n", all[y][i].first); } else puts("-1"); } return 0; }