Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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.