Problem G	Road Construction
Time Limit	5 Seconds

Bangladesh Government is seriously thinking about decreasing the intolerable traffic jam in Dhaka. They have tried lots of things to solve this problem. But all of you know while traveling in Dhaka, it is almost impossible to escape it L. The higher authority of Government has now realized the situation that they need different view and doings for this Herculean task. They come to you and as an expertise in computer science you give them a solution. The idea is simple, to construct new roads. But the problem is to ensure that the newly constructed road is properly utilized. And that will happen only if traveling cost is reduced for some routes. In that case traffic in those routes will automatically use the current road and thus will be distributed better in the network.

In this problem you will be given a map of Dhaka in terms of an undirected graph. Each node will denote a station and edge will represent a road. Nodes will be simple 2-D geometric points and the cost to travel a road is proportional to the Euclidian distance between two nodes. Now, you will suggest to construct one road temporarily. You have fixed the criterion to select the two nodes between which new road will be constructed.

·        If there is a road between (u, v) then this pair will not be considered.
·        Otherwise C_uv = Sum (PreCost_ij -CurCost_ij) where CurCost_ij is the shortest cost path from i to j if the road between (u, v) exists. And PreCost_ij is the shortest cost route before constructing the road between u and v.
·        The (u, v) pair with maximum C_uv will be selected.

Input
Each test case starts with two positive integers N (≤ 50) and M (≤ 1225).  In next few lines the coordinates (x, y) of the nodes will be given. The value of each coordinate will be in the range of -1000 to 1000. In next few lines the road description will be given. Each road consists of two positive integers (u, v) where 1 ≤ u, v ≤ N. It means that there is a bidirectional road between u and v. It is guaranteed that the graph will be connected.

Input is terminated by N = M = 0. This case should not be processed.

Output
If new road construction helps the traffic condition then output will be a pair of nodes (u, v) between which the new road will be constructed. If there are several candidates then the shortest distant nodes will be eligible. If again draw occurs then node pair whose indices are small will be the answer.

On the other hand if the road network is balanced (New road will not improve the traffic situation), print “No road required”. Note that, if C_uv is less or equal to 1.0 then the network will be considered balanced.

Sample Input	Output for Sample Input
4 6 0 0 0 2 2 0 2 2 1 2 1 3 1 4 2 3 2 4 3 4 4 4 0 0 0 2 2 0 2 2 1 2 2 3 3 4 4 1 4 3 0 0 0 2 2 0 2 2 1 2 2 3 3 4 0 0	No road required 1 3 1 3