#include <vector>
#include <string>
#include <fstream>
#include <set>
#include <stack>
#include <iostream>

using std::string;
using std::vector;
using std::ifstream;
using std::ofstream;
using std::pair;
using std::set;
using std::stack;

#define point pair<int, int>
#define arc pair<int, int>

#define x first
#define y second

#define nod first
#define cost second

#define oo 0x3f3f3f3f

class Nota10 {
private:
	string input_file;
	string output_file;
	int n, m, source, destination;
	vector<point> points;
	vector<arc>* graf;
	vector<int> distance, prev;

	inline int meters(point p1, point p2) {
		return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
	}

	void read() {
		ifstream in(input_file);
		in >> n >> m;

		graf = new vector<arc>[n + 1];
		distance.resize(n + 1, oo);
		points.resize(n + 1);
		prev.resize(n + 1, -1);

		int x, y;
		for (int i = 1; i <= n; ++i) {
			in >> x >> y;
			points[i] = std::make_pair(x, y);
		}

		for (int i = 1; i <= m; ++i) {
			in >> x >> y;
			int dist = meters(points[x], points[y]);
			graf[x].push_back(std::make_pair(y, dist));
			graf[y].push_back(std::make_pair(x, dist));
		}

		in.close();
	}

	void solve() {
		read();
		
		set<pair<int, int>> heap;
		heap.insert(std::make_pair(0, source));
		distance[source] = 0;

		while (!heap.empty()) {
			int first = heap.begin()->second;
			heap.erase(heap.begin());

			for (const auto& muchie : graf[first]) {
				if (distance[muchie.nod] > distance[first] + muchie.cost) {
					if (distance[muchie.nod] != oo) {
						heap.erase(heap.find(std::make_pair(distance[muchie.nod], muchie.nod)));
					}
					prev[muchie.nod] = first;
					distance[muchie.nod] = distance[first] + muchie.cost;
					heap.insert(std::make_pair(distance[muchie.nod], muchie.nod));
				}
			}
		}
	}

public:
	Nota10(const string& input_file, const string& output_file, const int& source, const int& destination) : input_file{ input_file }, output_file{ output_file }, source{ source }, destination{ destination }{};

	void print() {
		solve();

		ofstream out(output_file);

		out << sqrt(distance[destination]) << '\n';
		int nod = destination;
		std::stack<int> s;
		while (nod != -1) {
			s.push(nod);
			std::cout << nod << " ";
			nod = prev[nod];
		}

		while (!s.empty()) {
			nod = s.top();
			s.pop();
			out << nod << " ";
		}

		out.close();
	}

	~Nota10() {
		delete[] graf;
	}
};

int main() {

	Nota10 n = Nota10("10.in", "10.out", 1, 5);
	n.print();

	return 0;
}