시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB199186429439430.738%

문제

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

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

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

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

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

입력

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

두 번째 줄부터 $N$개의 줄에는 황선자를 포함하여 우주신들의 좌표가 $X$, $Y$ ($0 \le X, Y \le 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+XHJcblxyXG48cD5cdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWFjZmNcdWM3NTggXHVhZDUwXHVhYzEwXHVjNzQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1YWNmYyBcdWQ2NjlcdWMxMjBcdWM3OTBcdWM1MjggXHVkNjM5XHVjNzQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNCBcdWIwN2NcdWI5YWMgXHVjNzc0XHVjNWI0XHVjOWM0IFx1YzgxNVx1YzJlMFx1YzgwMVx1Yzc3OCBcdWQxYjVcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1Yzc3NFx1YjhlOFx1YzViNCBcdWM5YzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWFjZmMgXHVhZDUwXHVhYzEwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWQ3OThcdWI0ZTAgXHVjNzdjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ2NjlcdWMxMjBcdWM3OTBcdWM1MjhcdWIyOTQgXHVjNzc0XHViN2YwIFx1ZDFiNVx1Yjg1Y1x1YjRlNFx1Yzc3NCBcdWFlMzQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzY1Y1x1YjBkMFx1ZDU1OFx1YmE3NCBcdWQxYjVcdWI4NWNcdWI0ZTRcdWM3NzQgXHVhZTM4IFx1YzIxOFx1Yjg1ZCBcdWIzNTQgXHVkNzk4XHVjNzc0IFx1YjRlNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWM2YjBcdWI5YWNcdWI0ZTRcdWM3NDAgM1x1Y2MyOFx1YzZkMCBcdWM4OGNcdWQ0NWNcdWFjYzRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTM4XHVjMGMxXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHVjNmIwXHVjOGZjXHVjMmUwXHViNGU0XHVhY2ZjIFx1ZDY2OVx1YzEyMFx1Yzc5MFx1YzUyOFx1YjI5NCAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YWNjNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMzhcdWMwYzFcdWM1ZDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkMWI1XHViODVjXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YWNjNFx1YzBjMVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWJiZjggXHVkNjY5XHVjMTIwXHVjNzkwXHVjNTI4XHVjNjQwIFx1YzVmMFx1YWNiMFx1YjQxYywgXHVkNjM5XHVjNzQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkMWI1XHViODVjXHViNGU0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1ZDY2OVx1YzEyMFx1Yzc5MCBcdWM1MjhcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzU0NFx1YzljMSBcdWM1ZjBcdWFjYjBcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM2YjBcdWM4ZmNcdWMyZTBcdWI0ZTRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTc0IFx1YjRkY1x1YjgyNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzBjOFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTYwIFx1YzgxNVx1YzJlMFx1YzgwMVx1Yzc3OCBcdWQxYjVcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViNGU0XHVjNzc0IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVhYzhjIFx1ZDFiNVx1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgJmxkcXVvO1x1YmU3NVx1YzBjMSZyZHF1bztcdWM3NDQgXHVjNjc4XHVjZTYwXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiMFx1YzhmY1x1YzJlMFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kICgkMSBcXGxlIDFcXCwwMDAkKSBcdWM3NzRcdWJiZjggXHVjNWYwXHVhY2IwXHViNDFjIFx1YzJlMFx1YjRlNFx1YWNmY1x1Yzc1OCBcdWQxYjVcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4JE0kICgkMSBcXGxlIE0gXFxsZSAxXFwsMDAwJClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDY2OVx1YzEyMFx1Yzc5MFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM1ZWMgXHVjNmIwXHVjOGZjXHVjMmUwXHViNGU0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCAkWCQsICRZJCAoJDAgXFxsZSBYLCBZIFxcbGUgMVxcLDAwMFxcLDAwMCQpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YmMxMVx1YzczY1x1Yjg1YyAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3NFx1YmJmOCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkMWI1XHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYzg4XHVkNjM4XHViMjk0IFx1YzcwNFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWJjMWJcdWM3NDAgXHVjODhjXHVkNDVjXHViNGU0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjc3Y1x1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU2MCBcdWNkNWNcdWMxOGNcdWM3NTggXHVkMWI1XHViODVjIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWMxOGNcdWMyMThcdWM4MTAgXHViNDU4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4oMSwxKSAoMywxKSAoMiwzKSAoNCwzKSBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjNmIwXHVjOGZjXHVjMmUwXHViNGU0XHVhY2ZjIFx1ZDY2OVx1YzEyMFx1Yzc5MFx1YzUyOFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVhY2UwIDFcdWJjODhcdWQ1NThcdWFjZTAgNFx1YmM4OFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI4MDdcdWIyZTRcdWJhNzQgMVx1YmM4OFx1ZDU1OFx1YWNlMCAyXHViYzg4XHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWQxYjVcdWI4NWNcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIDNcdWJjODhcdWQ1NThcdWFjZTAgNFx1YmM4OFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVkMWI1XHViODVjXHViOTdjIFx1YjljY1x1YjRlNFx1YmE3NCBcdWMyZTBcdWI0ZTRcdWFjZmMgXHVjMTIwXHVjNzkwXHVjNTI4XHViMDdjXHViOWFjIFx1YjJlNCBcdWIzYzRcdWIyZWNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0XHVjMTFjIFx1YjM1NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTYwIFx1ZDFiNVx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3NzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCdWlsZGluZyBSb2FkcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFkIGp1c3QgYWNxdWlyZWQgc2V2ZXJhbCBuZXcgZmFybXMhIEhlIHdhbnRzIHRvIGNvbm5lY3QgdGhlIGZhcm1zIHdpdGggcm9hZHMgc28gdGhhdCBoZSBjYW4gdHJhdmVsIGZyb20gYW55IGZhcm0gdG8gYW55IG90aGVyIGZhcm0gdmlhIGEgc2VxdWVuY2Ugb2Ygcm9hZHM7IHJvYWRzIGFscmVhZHkgY29ubmVjdCBzb21lIG9mIHRoZSBmYXJtcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwKSBmYXJtcyAoY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4pIGlzIHJlcHJlc2VudGVkIGJ5IGEgcG9zaXRpb24gKFhfaSwgWV9pKSBvbiB0aGUgcGxhbmUgKDAgJmx0Oz0gWF9pICZsdDs9IDEsMDAwLDAwMDsgMCAmbHQ7PSBZX2kgJmx0Oz0gMSwwMDAsMDAwKS4gJm5ic3A7R2l2ZW4gdGhlIHByZWV4aXN0aW5nIE0gcm9hZHMgKDEgJmx0Oz0gTSAmbHQ7PSAxLDAwMCkgYXMgcGFpcnMgb2YgY29ubmVjdGVkIGZhcm1zLCBoZWxwIEZhcm1lciBKb2huIGRldGVybWluZSB0aGUgc21hbGxlc3QgbGVuZ3RoIG9mIGFkZGl0aW9uYWwgcm9hZHMgaGUgbXVzdCBidWlsZCB0byBjb25uZWN0IGFsbCBoaXMgZmFybXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTTxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFhfaSBhbmQgWV9pPFwvbGk+XHJcblx0PGxpPkxpbmVzIE4rMi4uTitNKzI6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IGkgYW5kIGosIGluZGljYXRpbmcgdGhhdCB0aGVyZSBpcyBhbHJlYWR5IGEgcm9hZCBjb25uZWN0aW5nIHRoZSBmYXJtIGkgYW5kIGZhcm0gai48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBTbWFsbGVzdCBsZW5ndGggb2YgYWRkaXRpb25hbCByb2FkcyByZXF1aXJlZCB0byBjb25uZWN0IGFsbCBmYXJtcywgcHJpbnRlZCByb3VuZGluZyB0byB0d28gZGVjaW1hbCBwbGFjZXMuIEJlIHN1cmUgdG8gY2FsY3VsYXRlIGRpc3RhbmNlcyBhcyA2NC1iaXQgZmxvYXRpbmcgcG9pbnQgbnVtYmVycy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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