#include <bits/stdc++.h> using namespace std; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} using Int = long long; const char newl = '\n'; struct Precision{ Precision(){ cout<<fixed<<setprecision(12); } }precision_beet; //INSERT ABOVE HERE using D = double; const int MAX = 2020; D dist[MAX][MAX]; signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m,k; cin>>n>>m>>k; int x,y; cin>>x>>y; x--;y--; for(int i=0;i<MAX;i++) for(int j=0;j<MAX;j++) dist[i][j]=-1; vector<D> ps(n),qs(n); for(int i=0;i<n;i++) cin>>ps[i]>>qs[i]; vector<vector<int>> G(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; D d=hypot(ps[u]-ps[v],qs[u]-qs[v]); dist[u][v]=dist[v][u]=d; G[u].emplace_back(v); G[v].emplace_back(u); } struct Path{ vector<int> vs; bool isvalid(int nxt){ assert(!vs.empty()); //cerr<<"sz:"<<vs.size()<<endl; //cerr<<vs.back()<<' '<<nxt<<endl; //cerr<<dist[vs.back()][nxt]<<endl; if(dist[vs.back()][nxt]<0) return false; //cerr<<"sz:"<<vs.size()<<endl; if(count(vs.begin(),vs.end(),nxt)) return false; //cerr<<"sz:"<<vs.size()<<endl; return true; //cerr<<"sz:"<<vs.size()<<endl; } D len; bool operator<(const Path &o)const{ if(len!=o.len) return len<o.len; return vs<o.vs; }; bool operator>(const Path &o)const{ if(len!=o.len) return len>o.len; return vs>o.vs; }; }; priority_queue<Path, vector<Path>, greater<Path>> pq; vector<set<Path>> dp(n); auto push=[&](Path p){ // cerr<<p.vs.back()<<endl; // cerr<<dp[p.vs.back()].size()<<endl; if(dp[p.vs.back()].count(p)) return; dp[p.vs.back()].emplace(p); pq.emplace(p); }; { Path p; p.vs.emplace_back(x); p.len=0; push(p); } vector<int> cnt(n,0); while(!pq.empty()){ Path p=pq.top();pq.pop(); int v=p.vs.back(); // cerr<<v<<' '<<p.len<<endl; cnt[v]++; if(cnt[y]==k) break; if(cnt[v]>k) continue; for(int u:G[v]){ // cerr<<v<<"->"<<u<<endl; if(!p.isvalid(u)) continue; // cerr<<v<<"->"<<u<<endl; p.vs.emplace_back(u); p.len+=dist[v][u]; push(p); p.vs.pop_back(); p.len-=dist[v][u]; } } for(int i=0;i<k;i++){ if(dp[y].empty()){ cout<<-1<<newl; continue; } cout<<dp[y].begin()->len<<newl; dp[y].erase(dp[y].begin()); } return 0; }