시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 929 279 166 27.393%

문제

황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.

하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다.

우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을  좋아하지 않는다. 왜냐하면 통로들이 길 수록 더 힘이 들기 때문이다.

또한 우리들은 3차원 좌표계로 나타낼 수 있는 세상에 살고 있지만 우주신들과 황선자씨는 2차원 좌표계로 나타낼 수 있는 세상에 살고 있다. 통로들의 길이는 2차원 좌표계상의 거리와 같다.

이미 황선자씨와 연결된, 혹은 우주신들과 연결된 통로들이 존재한다. 우리는 황선자 씨를 도와 아직 연결이 되지 않은 우주신들을 연결해 드려야 한다. 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자.

입력

첫째 줄에 우주신들의 개수(N<=1,000) 이미 연결된 신들과의 통로의 개수(M<=1,000)가 주어진다.

두 번째 줄부터 N개의 줄에는 황선자를 포함하여 우주신들의 좌표가 (0<= X<=1,000,000), (0<=Y<=1,000,000)가 주어진다. 그 밑으로 M개의 줄에는 이미 연결된 통로가 주어진다. 번호는 위의 입력받은 좌표들의 순서라고 생각하면 된다. 좌표는 정수이다.

출력

첫째 줄에 만들어야 할 최소의 통로 길이를 출력하라. 출력은 소수점 둘째짜리까지 출력하여라.

예제 입력 1

4 1
1 1
3 1
2 3
4 3
1 4

예제 출력 1

4.00

힌트

(1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼리 다 도달이 가능하면서 더 만들어야 할 통로의 길이는 최소가 된다.

W3sicHJvYmxlbV9pZCI6IjE3NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YjBcdWM4ZmNcdWMyZTBcdWFjZmNcdWM3NTggXHVhZDUwXHVhYzEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2NjlcdWMxMjBcdWM3OTBcdWM1MjhcdWIyOTQgXHVjNmIwXHVjOGZjXHVjMmUwXHVhY2ZjIFx1YWQ1MFx1YWMxMFx1Yzc0NCBcdWQ1NjBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2M0NFx1YjExMFx1YjdlYyBcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM2YjBcdWM4ZmNcdWMyZTBcdWM3NDAgXHVkNTU4XHViMDk4XHViOWNjIFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHVhZTMwXHViNTRjXHViYjM4XHVjNWQwIFx1ZDY2OVx1YzEyMFx1Yzc5MCBcdWM1MjhcdWIyOTQgXHViOWU0XHViYzg4IFx1YzVlY1x1YjdmZlx1Yzc1OCBcdWM2YjBcdWM4ZmNcdWMyZTBcdWFjZmMgXHVhZDUwXHVhYzEwXHVkNTU4XHViMjkwXHViNzdjIFx1ZDc5OFx1Yzc3NCBcdWI0ZTBcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1YjM1OCBcdWM2NDBcdWM5MTFcdWM1ZDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1Yzc3NCBcdWQ2NjlcdWMxMjBcdWM3OTBcdWM1MjhcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzcwNFx1YjMwMFx1ZDU1YyBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWM3NDAgXHViYzE0XHViODVjIFx1ZDY2OVx1YzEyMFx1Yzc5MFx1YzUyOFx1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MjAgXHVkNTQ0XHVjNjk0XHVhYzAwIFx1YzVjNlx1YjJlNC4gXHVjNzc0XHViYmY4IFx1ZDY2OVx1YzEyMFx1Yzc5MFx1YzUyOFx1YzY0MCBcdWQ2MzlcdWM3NDAgXHVjNzc0XHViYmY4IFx1YzZiMFx1YzhmY1x1YzJlMFx1YjA3Y1x1YjlhYyBcdWFkNTBcdWFjMTBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWM3NzQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNmIwXHVjOGZjXHVjMmUwXHViNGU0XHVjNzQwIFx1YWRmOCBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWM3NDQgXHVhYzcwXHVjY2QwXHVjMTFjIFx1ZDY2OVx1YzEyMFx1Yzc5MCBcdWM1MjhcdWM2NDAgXHVhZDUwXHVhYzEwXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWFjZmNcdWM3NTggXHVhZDUwXHVhYzEwXHVjNzQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1YWNmYyBcdWQ2NjlcdWMxMjBcdWM3OTBcdWM1MjggXHVkNjM5XHVjNzQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNCBcdWIwN2NcdWI5YWMgXHVjNzc0XHVjNWI0XHVjOWM0IFx1YzgxNVx1YzJlMFx1YzgwMVx1Yzc3OCBcdWQxYjVcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1Yzc3NFx1YjhlOFx1YzViNCBcdWM5YzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWFjZmMgXHVhZDUwXHVhYzEwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWQ3OThcdWI0ZTAgXHVjNzdjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ2NjlcdWMxMjBcdWM3OTBcdWM1MjhcdWIyOTQgXHVjNzc0XHViN2YwIFx1ZDFiNVx1Yjg1Y1x1YjRlNFx1Yzc3NCBcdWFlMzQgXHVhYzgzXHVjNzQ0Jm5ic3A7IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzY1Y1x1YjBkMFx1ZDU1OFx1YmE3NCBcdWQxYjVcdWI4NWNcdWI0ZTRcdWM3NzQgXHVhZTM4IFx1YzIxOFx1Yjg1ZCBcdWIzNTQgXHVkNzk4XHVjNzc0IFx1YjRlNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWM2YjBcdWI5YWNcdWI0ZTRcdWM3NDAgM1x1Y2MyOFx1YzZkMCBcdWM4OGNcdWQ0NWNcdWFjYzRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTM4XHVjMGMxXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHVjNmIwXHVjOGZjXHVjMmUwXHViNGU0XHVhY2ZjIFx1ZDY2OVx1YzEyMFx1Yzc5MFx1YzUyOFx1YjI5NCAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YWNjNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMzhcdWMwYzFcdWM1ZDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkMWI1XHViODVjXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YWNjNFx1YzBjMVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWJiZjggXHVkNjY5XHVjMTIwXHVjNzkwXHVjNTI4XHVjNjQwIFx1YzVmMFx1YWNiMFx1YjQxYywgXHVkNjM5XHVjNzQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkMWI1XHViODVjXHViNGU0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1ZDY2OVx1YzEyMFx1Yzc5MCBcdWM1MjhcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzU0NFx1YzljMSBcdWM1ZjBcdWFjYjBcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTc0IFx1YjRkY1x1YjgyNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzBjOFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTYwIFx1YzgxNVx1YzJlMFx1YzgwMVx1Yzc3OCBcdWQxYjVcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViNGU0XHVjNzc0IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVhYzhjIFx1ZDFiNVx1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgJmxkcXVvO1x1YmU3NVx1YzBjMSZyZHF1bztcdWM3NDQgXHVjNjc4XHVjZTYwXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMTgoTiZsdDs9MSwwMDApIFx1Yzc3NFx1YmJmOCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVjMmUwXHViNGU0XHVhY2ZjXHVjNzU4IFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMTgoTSZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjY5XHVjMTIwXHVjNzkwXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYyBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwICgwJmx0Oz0gWCZsdDs9MSwwMDAsMDAwKSwmbmJzcDsoMCZsdDs9WSZsdDs9MSwwMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWJjMTFcdWM3M2NcdWI4NWMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzc0XHViYmY4IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWQxYjVcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjNzA0XHVjNzU4IFx1Yzc4NVx1YjgyNVx1YmMxYlx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWI0ZTRcdWM3NTggXHVjMjFjXHVjMTFjXHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTYwIFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWQxYjVcdWI4NWMgXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4gXHVjZDljXHViODI1XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWI0NThcdWM5ZjhcdWM5ZGNcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4oMSwxKSAoMywxKSAoMiwzKSAoNCwzKSBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjNmIwXHVjOGZjXHVjMmUwXHViNGU0XHVhY2ZjIFx1ZDY2OVx1YzEyMFx1Yzc5MFx1YzUyOFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVhY2UwIDFcdWJjODhcdWQ1NThcdWFjZTAgNFx1YmM4OFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI4MDdcdWIyZTRcdWJhNzQgMVx1YmM4OFx1ZDU1OFx1YWNlMCAyXHViYzg4XHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWQxYjVcdWI4NWNcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIDNcdWJjODhcdWQ1NThcdWFjZTAgNFx1YmM4OFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVkMWI1XHViODVjXHViOTdjIFx1YjljY1x1YjRlNFx1YmE3NCBcdWMyZTBcdWI0ZTRcdWFjZmMgXHVjMTIwXHVjNzkwXHVjNTI4XHViMDdjXHViOWFjIFx1YjJlNCBcdWIzYzRcdWIyZWNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0XHVjMTFjIFx1YjM1NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTYwIFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3NzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCdWlsZGluZyBSb2FkcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFkIGp1c3QgYWNxdWlyZWQgc2V2ZXJhbCBuZXcgZmFybXMhIEhlIHdhbnRzIHRvIGNvbm5lY3QgdGhlIGZhcm1zIHdpdGggcm9hZHMgc28gdGhhdCBoZSBjYW4gdHJhdmVsIGZyb20gYW55IGZhcm0gdG8gYW55IG90aGVyIGZhcm0gdmlhIGEgc2VxdWVuY2Ugb2Ygcm9hZHM7IHJvYWRzIGFscmVhZHkgY29ubmVjdCBzb21lIG9mIHRoZSBmYXJtcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwKSBmYXJtcyAoY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4pIGlzIHJlcHJlc2VudGVkIGJ5IGEgcG9zaXRpb24gKFhfaSwgWV9pKSBvbiB0aGUgcGxhbmUgKDAgJmx0Oz0gWF9pICZsdDs9IDEsMDAwLDAwMDsgMCAmbHQ7PSBZX2kgJmx0Oz0gMSwwMDAsMDAwKS4gJm5ic3A7R2l2ZW4gdGhlIHByZWV4aXN0aW5nIE0gcm9hZHMgKDEgJmx0Oz0gTSAmbHQ7PSAxLDAwMCkgYXMgcGFpcnMgb2YgY29ubmVjdGVkIGZhcm1zLCBoZWxwIEZhcm1lciBKb2huIGRldGVybWluZSB0aGUgc21hbGxlc3QgbGVuZ3RoIG9mIGFkZGl0aW9uYWwgcm9hZHMgaGUgbXVzdCBidWlsZCB0byBjb25uZWN0IGFsbCBoaXMgZmFybXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTTxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk4rMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogWF9pIGFuZCBZX2k8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyBOKzIuLk4rTSsyOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBpIGFuZCBqLCBpbmRpY2F0aW5nIHRoYXQgdGhlcmUgaXMgYWxyZWFkeSBhIHJvYWQgY29ubmVjdGluZyB0aGUgZmFybSBpIGFuZCBmYXJtIGouPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFNtYWxsZXN0IGxlbmd0aCBvZiBhZGRpdGlvbmFsIHJvYWRzIHJlcXVpcmVkIHRvIGNvbm5lY3QgYWxsIGZhcm1zLCBwcmludGVkIHdpdGhvdXQgcm91bmRpbmcgdG8gdHdvIGRlY2ltYWwgcGxhY2VzLiBCZSBzdXJlIHRvIGNhbGN1bGF0ZSBkaXN0YW5jZXMgYXMgNjQtYml0IGZsb2F0aW5nIHBvaW50IG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO December 2007 Contest > Silver 2번