시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 799 231 137 26.245%

문제

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

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

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

또한 우리들은 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+XHViNDUwIFx1YmM4OFx1YzlmOFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2NjlcdWMxMjBcdWM3OTBcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgKDAmbHQ7PSBYJmx0Oz0xLDAwMCwwMDApLCZuYnNwOygwJmx0Oz1ZJmx0Oz0xLDAwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YmMxMVx1YzczY1x1Yjg1YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzRcdWJiZjggXHVjNWYwXHVhY2IwXHViNDFjIFx1ZDFiNVx1Yjg1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWM3MDRcdWM3NTggXHVjNzg1XHViODI1XHViYzFiXHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1YjRlNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI3N2NcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjODhjXHVkNDVjXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NjAgXHVjZDVjXHVjMThjXHVjNzU4IFx1ZDFiNVx1Yjg1YyBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOFx1YzlkY1x1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPigxLDEpICgzLDEpICgyLDMpICg0LDMpIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWFjZmMgXHVkNjY5XHVjMTIwXHVjNzkwXHVjNTI4XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWFjZTAgMVx1YmM4OFx1ZDU1OFx1YWNlMCA0XHViYzg4XHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YjJlNFx1YmE3NCAxXHViYzg4XHVkNTU4XHVhY2UwIDJcdWJjODhcdWM3NDQgXHVjNzg3XHViMjk0IFx1ZDFiNVx1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgM1x1YmM4OFx1ZDU1OFx1YWNlMCA0XHViYzg4XHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWQxYjVcdWI4NWNcdWI5N2MgXHViOWNjXHViNGU0XHViYTc0IFx1YzJlMFx1YjRlNFx1YWNmYyBcdWMxMjBcdWM3OTBcdWM1MjhcdWIwN2NcdWI5YWMgXHViMmU0IFx1YjNjNFx1YjJlY1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzRcdWMxMWMgXHViMzU0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NjAgXHVkMWI1XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTc3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJ1aWxkaW5nIFJvYWRzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYWQganVzdCBhY3F1aXJlZCBzZXZlcmFsIG5ldyBmYXJtcyEgSGUgd2FudHMgdG8gY29ubmVjdCB0aGUgZmFybXMgd2l0aCByb2FkcyBzbyB0aGF0IGhlIGNhbiB0cmF2ZWwgZnJvbSBhbnkgZmFybSB0byBhbnkgb3RoZXIgZmFybSB2aWEgYSBzZXF1ZW5jZSBvZiByb2Fkczsgcm9hZHMgYWxyZWFkeSBjb25uZWN0IHNvbWUgb2YgdGhlIGZhcm1zLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBOICgxICZsdDs9IE4gJmx0Oz0gMSwwMDApIGZhcm1zIChjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTikgaXMgcmVwcmVzZW50ZWQgYnkgYSBwb3NpdGlvbiAoWF9pLCBZX2kpIG9uIHRoZSBwbGFuZSAoMCAmbHQ7PSBYX2kgJmx0Oz0gMSwwMDAsMDAwOyAwICZsdDs9IFlfaSAmbHQ7PSAxLDAwMCwwMDApLiAmbmJzcDtHaXZlbiB0aGUgcHJlZXhpc3RpbmcgTSByb2FkcyAoMSAmbHQ7PSBNICZsdDs9IDEsMDAwKSBhcyBwYWlycyBvZiBjb25uZWN0ZWQgZmFybXMsIGhlbHAgRmFybWVyIEpvaG4gZGV0ZXJtaW5lIHRoZSBzbWFsbGVzdCBsZW5ndGggb2YgYWRkaXRpb25hbCByb2FkcyBoZSBtdXN0IGJ1aWxkIHRvIGNvbm5lY3QgYWxsIGhpcyBmYXJtcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTisxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBYX2kgYW5kIFlfaTxcL3A+XHJcblxyXG48cD4qIExpbmVzIE4rMi4uTitNKzI6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IGkgYW5kIGosIGluZGljYXRpbmcgdGhhdCB0aGVyZSBpcyBhbHJlYWR5IGEgcm9hZCBjb25uZWN0aW5nIHRoZSBmYXJtIGkgYW5kIGZhcm0gai48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogU21hbGxlc3QgbGVuZ3RoIG9mIGFkZGl0aW9uYWwgcm9hZHMgcmVxdWlyZWQgdG8gY29ubmVjdCBhbGwgZmFybXMsIHByaW50ZWQgd2l0aG91dCByb3VuZGluZyB0byB0d28gZGVjaW1hbCBwbGFjZXMuIEJlIHN1cmUgdG8gY2FsY3VsYXRlIGRpc3RhbmNlcyBhcyA2NC1iaXQgZmxvYXRpbmcgcG9pbnQgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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