race

The mayor of Plovdiv decides to arrange a car race on the streets of Plovdiv to show that the streets of the city are really suitable for fast driving. He has to choose the route for the race, so this route should be as fast as possible. After talking with his advisors, he came up with the following constraints. The race must start and finish at the crossroad where the City Hall is. The only permitted turns along the track are left turns (to make a left turn means to change driving direction to the left in respect to the current forward direction by any angle greater than or equal to 0 and strictly less than 180 degrees). Moreover, among all routes, satisfying the above conditions, the chosen route should have the following property: the length of the shortest street from the route should be as long as possible.<br><br>
The city of Plovdiv has N crossroads and M two-way streets connecting them. The crossroads are described with their two coordinates in the plane and numbered from 1 to N in the order they are given in the input. The City Hall is situated at the crossroad with number 1. The streets are straight line segments starting at one crossroad and finishing at another. The length of a street is equal to the Euclidean distance between its two ends. A street is described by the numbers of its two ends. There is no more than one street between any two crossroads. The streets do not intersect themselves except at their endpoints. <br><br>
Write a program RACE to find which route, among all possible routes in the city, starts and finishes at crossroad 1 and at each crossroad this route goes either straightforward or makes a left turn, and the shortest street in this route is as long as possible. The route cannot pass twice in the same direction in the same street. <br><br>
The first line of the standard input contains the two numbers N and M, 3 <= N <= 2000, 5 <= M <= 25000, separated by a space. Each of the next N lines contains coordinates X and Y of the given crossroads, separated by a space. These coordinates are integers from the interval
[–10000, 10000]. Last M lines describe the streets. Each of these lines contains two crossroads’ numbers, which are connected by a street. <br><br>
The standard output should contain a description of the route. The first line should contain the count of the crossroads in the route (twice including crossroad 1 as the first and the last in the route). The next line should contain the numbers of the crossroads along the route (starting and ending with crossroad 1) in the proper order, separated by a space. <br><br>
There is at least one solution of the task. If there is more than one solution, output an arbitrary one of them. <br><br>

EXAMPLE<br><br>
Input<br>
5 6<br>
1 0<br>
2 1<br>
1 1<br>
0 1<br>
1 2<br>
1 2<br>
2 5<br>
1 4<br>
5 4<br>
2 3<br>
4 3<br><br>
Output<br>
5<br>
1 2 5 4 1