시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 526 90 55 15.152%

문제

전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을 수록 좋다.

크기가 N×M인 비어있는 회로판에서 두 점 A1과 A2, 그리고 B1와 B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안된다. 이 경우에 필요한 전선의 길이의 최소값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다.

입력

첫째 줄에 회로판의 크기 N과 M이 주어진다. (2 ≤ N, M ≤ 100) 

다음 네 줄에는 A1, A2, B1, B2의 좌표가 주어진다. 점의 좌표는 두 정수의 쌍으로 이루어져 있고, 첫번째 좌표는 0 이상 N 이하이며 두번째 좌표는 0 이상 M 이하이다. 어떤 점도 같은 위치에 있지 않다.

출력

A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최소값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

6 6
2 1
5 4
4 0
4 5

예제 출력 1

15
W3sicHJvYmxlbV9pZCI6IjUwMjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjBcdWFjYjAiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY29ubmVjdC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTMzcHg7IHdpZHRoOjEyOHB4XCIgXC8+XHVjODA0XHVhZTMwIFx1ZDY4Y1x1Yjg1Y1x1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwXHVjNzQ0IFx1YzgwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM3NDQgXHViNTRjLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjOWU3XHVjNzQ0IFx1YzIxOFx1Yjg1ZCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBOJnRpbWVzO01cdWM3NzggXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDY4Y1x1Yjg1Y1x1ZDMxMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwIEExXHVhY2ZjIEEyLCBcdWFkZjhcdWI5YWNcdWFjZTAgQjFcdWM2NDAgQjJcdWI5N2MgXHVjODA0XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM3NzRcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MDRcdWMxMjBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWMyMThcdWM5YzEsIFx1YzIxOFx1ZDNjOVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzQwIFx1YzgxMVx1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzgwNFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4MDRcdWMxMjBcdWM3NDAgXHVkNjhjXHViODVjXHVkMzEwIFx1YmMxNFx1YWU2NVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjhjXHViODVjXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4sIE0gJmxlOyAxMDApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWIxMjQgXHVjOTA0XHVjNWQwXHViMjk0IEExLCBBMiwgQjEsIEIyXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWMzMGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjY2FiXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAwIFx1Yzc3NFx1YzBjMSBOIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YmE3MCBcdWI0NTBcdWJjODhcdWM5ZjggXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIE0gXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjODEwXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BMVx1YWNmYyBBMiwgXHVhZGY4XHViOWFjXHVhY2UwIEIxXHVhY2ZjIEIyXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODA0XHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTAyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbm5lY3QiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY29ubmVjdC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTMzcHg7IG9wYWNpdHk6MC45OyB3aWR0aDoxMjhweFwiIFwvPldoZW4gY29uc3RydWN0aW5nIGVsZWN0cmljIGNpcmN1aXRzIG9uZSBoYXMgdG8gY29ubmVjdCBwYWlycyBvZiBwb2ludHMgdXNpbmcgd2lyZSwgcHJlZmVyYWJsZSBhcyBzaG9ydCBhcyBwb3NzaWJsZS4gSW4gdGhpcyBwcm9ibGVtIHdlIGhhdmUgYW4gZW1wdHkgY2lyY3VpdCBib2FyZCBvZiBzaXplIE4mdGltZXM7TSB3aGVyZSB3ZSB3YW50IHRvIGNvbm5lY3QgdGhlIHR3byBwb2ludHMgQTEgYW5kIEEyIHdpdGggZWFjaCBvdGhlciB1c2luZyBvbmUgd2lyZSwgYW5kIHRoZSB0d28gcG9pbnRzIEIxIGFuZCBCMiB3aXRoIGVhY2ggb3RoZXIgdXNpbmcgYW5vdGhlciB3aXJlLiBUaGUgd2lyZXMgbXVzdCBnbyBhbG9uZyB0aGUgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgZWRnZXMgb2YgdGhlIGdyaWQgKHNlZSBndXJlKSwgYW5kIHRoZSB0d28gd2lyZXMgbWF5IG5vdCBzaGFyZSBhIGNvbW1vbiB2ZXJ0ZXguIERldGVybWluZSB0aGUgbWluaW11bSBsZW5ndGggb2Ygd2lyZSBuZWVkZWQgdG8gZG8gc28uIFRoZSB3aXJlIG1heSBub3QgZ28gb3V0c2lkZSB0aGUgY2lyY3VpdCBib2FyZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgTiAoMiAmbGU7IE4gJmxlOyAxMDApIGFuZCBNICgyICZsZTsgTSAmbGU7IDEwMCksIHRoZSBncmlkIHNpemUgb2YgdGhlIGNpcmN1aXQgYm9hcmQuPFwvcD5cclxuXHJcbjxwPlRoZW4gZm9sbG93cyBmb3VyIGxpbmVzIGNvbnRhaW5pbmcgdGhlIGNvb3JkaW5hdGVzIGZvciB0aGUgcG9pbnRzIEExLCBBMiwgQjEgYW5kIEIyLCByZXNwZWN0aXZlbHkuIEVhY2ggY29vcmRpbmF0ZSBwYWlyIHdpbGwgYmUgZGVzY3JpYmVkIHVzaW5nIHR3byBpbnRlZ2VycyBhbmQgd2lsbCBjb3JyZXNwb25kIHRvIGFuIGludGVyc2VjdGlvbiBwb2ludCBpbiB0aGUgZ3JpZC4gVGhlIHJzdCBjb29yZGluYXRlIHdpbGwgYmUgYmV0d2VlbiAwIGFuZCBOIGluY2x1c2l2ZSBhbmQgdGhlIHNlY29uZCBjb29yZGluYXRlIGJldHdlZW4gMCBhbmQgTSBpbmNsdXNpdmUuIEFsbCBjb29yZGluYXRlIHBhaXJzIHdpbGwgYmUgdW5pcXVlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW11bSBsZW5ndGggb2Ygd2lyZSBuZWVkZWQgdG8gY29ubmVjdCB0aGUgcG9pbnRzLCBvciAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7IGlmIGl0JiMzOTtzIG5vdCBwb3NzaWJsZSB0byBkbyBzby48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=