Кметът на Пловдив решава да организира автомобилно рали, за да покаже, че улиците на града наистина са подходящи за бързо шофиране. Той трябва да избере колкото може по-бърз маршрут. След като го обсъжда със своите съветници, той достига до следните ограничения. Ралито трябва да започва и да завършва на кръстовището, на което се намира сградата на общината. Единствените позволени завои по трасето са левите завои (да направите ляв завой означава да смените посоката на шофиране наляво относно текущата посока напред с някакъв ъгъл, по-голям или равен на нула и строго по-малък от 180 градуса). Нещо повече – измежду всички маршрути, удовлетворяващи горните условия, избраният маршрут трябва да удовлетворява следното свойство: дължината на най-късата улица от маршрута трябва да бъде възможно най-дълга
Град Пловдив има N кръстовища и M двупосочни улици, които ги свързват. Кръстовищата са описани с техните две координати в равнината и са номерирани от 1 до N в реда, в който са дадени на входа.. Сградата на общината се намира на кръстовище с номер 1. Улиците са отсечки, които започват от едно кръстовище и завършват на друго. Дължината на една улица е равна на евклидовото разстояние между двата й края. Улицата се описва с номерата на кръстовищата в двата й края. Няма повече от една улица между две кръстовища. Улиците не се пресичат другаде, освен в крайните си точки.
Напишете програма RACE, която намира кой маршрут измежду всички маршрути в града: започва и завършва на кръстовище 1; на всяко кръсовище или продължава направо, или завива наляво; най-късата улица в него е възможно най-дълга. Маршрутът не може да минава два пъти в същата посока по една и съща улица.
Първият ред от стандартния вход съдържа две числа N (3 ≤ N ≤ 2000) и M (5 ≤ M ≤ 25000), разделени с интервал. Всеки от следващите N реда съдържа координатите X и Y на дадените кръстовища, отделени с интервал. Тези координати са цели числа от интервала [‑10000, 10000]. Последните M реда описват улиците. Всеки от тях съдържа два номера на кръстовища, които са краища на тази улица.
Стандартният изход трябва да съдържа описанието на маршрута. Първият ред трябва да съдържа броя на кръстовищата в маршрута (два пъти се включва кръстовище 1, като първо и последно в маршрута). Следващият ред трябва да съдържа номерата на кръстовищата в маршрута (започват и завършват с 1) по реда на посещаването им, отделени с интервал
Задачата има поне едно решение. Ако има повече от едно, изведете което и да е от тях.
Вход Изход
5 6 5
1 0 1 2 5 4 1
2 1
1 1
0 1
1 2
1 2
2 5
1 4
5 4
2 3
4 3