시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 718 121 72 14.938%

문제

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

크기가 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+XHVjODA0XHVhZTMwIFx1ZDY4Y1x1Yjg1Y1x1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwXHVjNzQ0IFx1YzgwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM3NDQgXHViNTRjLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjOWU3XHVjNzQ0IFx1YzIxOFx1Yjg1ZCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBOJnRpbWVzO01cdWM3NzggXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDY4Y1x1Yjg1Y1x1ZDMxMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwIEExXHVhY2ZjIEEyLCBcdWFkZjhcdWI5YWNcdWFjZTAgQjFcdWM2NDAgQjJcdWI5N2MgXHVjODA0XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM3NzRcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MDRcdWMxMjBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWMyMThcdWM5YzEsIFx1YzIxOFx1ZDNjOVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzQwIFx1YzgxMVx1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzgwNFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4MDRcdWMxMjBcdWM3NDAgXHVkNjhjXHViODVjXHVkMzEwIFx1YmMxNFx1YWU2NVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjhjXHViODVjXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4sIE0gJmxlOyAxMDApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWIxMjQgXHVjOTA0XHVjNWQwXHViMjk0IEExLCBBMiwgQjEsIEIyXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWMzMGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4OGNcdWQ0NWNcdWIyOTQgMCBcdWM3NzRcdWMwYzEgTiBcdWM3NzRcdWQ1NThcdWM3NzRcdWJhNzAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4OGNcdWQ0NWNcdWIyOTQgMCBcdWM3NzRcdWMwYzEgTSBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM4MTBcdWIzYzQgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkExXHVhY2ZjIEEyLCBcdWFkZjhcdWI5YWNcdWFjZTAgQjFcdWFjZmMgQjJcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM4MDRcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDIyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29ubmVjdCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb25uZWN0LnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzNweDsgb3BhY2l0eTowLjk7IHdpZHRoOjEyOHB4XCIgXC8+V2hlbiBjb25zdHJ1Y3RpbmcgZWxlY3RyaWMgY2lyY3VpdHMgb25lIGhhcyB0byBjb25uZWN0IHBhaXJzIG9mIHBvaW50cyB1c2luZyB3aXJlLCBwcmVmZXJhYmxlIGFzIHNob3J0IGFzIHBvc3NpYmxlLiBJbiB0aGlzIHByb2JsZW0gd2UgaGF2ZSBhbiBlbXB0eSBjaXJjdWl0IGJvYXJkIG9mIHNpemUgTiZ0aW1lcztNIHdoZXJlIHdlIHdhbnQgdG8gY29ubmVjdCB0aGUgdHdvIHBvaW50cyBBMSBhbmQgQTIgd2l0aCBlYWNoIG90aGVyIHVzaW5nIG9uZSB3aXJlLCBhbmQgdGhlIHR3byBwb2ludHMgQjEgYW5kIEIyIHdpdGggZWFjaCBvdGhlciB1c2luZyBhbm90aGVyIHdpcmUuIFRoZSB3aXJlcyBtdXN0IGdvIGFsb25nIHRoZSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBlZGdlcyBvZiB0aGUgZ3JpZCAoc2VlIGd1cmUpLCBhbmQgdGhlIHR3byB3aXJlcyBtYXkgbm90IHNoYXJlIGEgY29tbW9uIHZlcnRleC4gRGV0ZXJtaW5lIHRoZSBtaW5pbXVtIGxlbmd0aCBvZiB3aXJlIG5lZWRlZCB0byBkbyBzby4gVGhlIHdpcmUgbWF5IG5vdCBnbyBvdXRzaWRlIHRoZSBjaXJjdWl0IGJvYXJkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzLCBOICgyICZsZTsgTiAmbGU7IDEwMCkgYW5kIE0gKDIgJmxlOyBNICZsZTsgMTAwKSwgdGhlIGdyaWQgc2l6ZSBvZiB0aGUgY2lyY3VpdCBib2FyZC48XC9wPlxyXG5cclxuPHA+VGhlbiBmb2xsb3dzIGZvdXIgbGluZXMgY29udGFpbmluZyB0aGUgY29vcmRpbmF0ZXMgZm9yIHRoZSBwb2ludHMgQTEsIEEyLCBCMSBhbmQgQjIsIHJlc3BlY3RpdmVseS4gRWFjaCBjb29yZGluYXRlIHBhaXIgd2lsbCBiZSBkZXNjcmliZWQgdXNpbmcgdHdvIGludGVnZXJzIGFuZCB3aWxsIGNvcnJlc3BvbmQgdG8gYW4gaW50ZXJzZWN0aW9uIHBvaW50IGluIHRoZSBncmlkLiBUaGUgcnN0IGNvb3JkaW5hdGUgd2lsbCBiZSBiZXR3ZWVuIDAgYW5kIE4gaW5jbHVzaXZlIGFuZCB0aGUgc2Vjb25kIGNvb3JkaW5hdGUgYmV0d2VlbiAwIGFuZCBNIGluY2x1c2l2ZS4gQWxsIGNvb3JkaW5hdGUgcGFpcnMgd2lsbCBiZSB1bmlxdWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIGxlbmd0aCBvZiB3aXJlIG5lZWRlZCB0byBjb25uZWN0IHRoZSBwb2ludHMsIG9yICZxdW90O0lNUE9TU0lCTEUmcXVvdDsgaWYgaXQmIzM5O3Mgbm90IHBvc3NpYmxlIHRvIGRvIHNvLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==