시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1586 294 199 17.595%

문제

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

크기가 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+XHVjODA0XHVhZTMwIFx1ZDY4Y1x1Yjg1Y1x1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwXHVjNzQ0IFx1YzgwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM3NDQgXHViNTRjLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjOWU3XHVjNzQ0IFx1YzIxOFx1Yjg1ZCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBOJnRpbWVzO01cdWM3NzggXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDY4Y1x1Yjg1Y1x1ZDMxMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwIEExXHVhY2ZjIEEyLCBcdWFkZjhcdWI5YWNcdWFjZTAgQjFcdWM2NDAgQjJcdWI5N2MgXHVjODA0XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM3NzRcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MDRcdWMxMjBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWMyMThcdWM5YzEsIFx1YzIxOFx1ZDNjOVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzQwIFx1YzgxMVx1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM4MDRcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjODA0XHVjMTIwXHVjNzQwIFx1ZDY4Y1x1Yjg1Y1x1ZDMxMCBcdWJjMTRcdWFlNjVcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY4Y1x1Yjg1Y1x1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOLCBNICZsZTsgMTAwKSZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHViMTI0IFx1YzkwNFx1YzVkMFx1YjI5NCBBMSwgQTIsIEIxLCBCMlx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NTggXHVjMzBkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIE4gXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIE0gXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjODEwXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BMVx1YWNmYyBBMiwgXHVhZGY4XHViOWFjXHVhY2UwIEIxXHVhY2ZjIEIyXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODA0XHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDIyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29ubmVjdCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb25uZWN0LnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzNweDsgb3BhY2l0eTowLjk7IHdpZHRoOjEyOHB4XCIgXC8+V2hlbiBjb25zdHJ1Y3RpbmcgZWxlY3RyaWMgY2lyY3VpdHMgb25lIGhhcyB0byBjb25uZWN0IHBhaXJzIG9mIHBvaW50cyB1c2luZyB3aXJlLCBwcmVmZXJhYmxlIGFzIHNob3J0IGFzIHBvc3NpYmxlLiBJbiB0aGlzIHByb2JsZW0gd2UgaGF2ZSBhbiBlbXB0eSBjaXJjdWl0IGJvYXJkIG9mIHNpemUgTiZ0aW1lcztNIHdoZXJlIHdlIHdhbnQgdG8gY29ubmVjdCB0aGUgdHdvIHBvaW50cyBBMSBhbmQgQTIgd2l0aCBlYWNoIG90aGVyIHVzaW5nIG9uZSB3aXJlLCBhbmQgdGhlIHR3byBwb2ludHMgQjEgYW5kIEIyIHdpdGggZWFjaCBvdGhlciB1c2luZyBhbm90aGVyIHdpcmUuIFRoZSB3aXJlcyBtdXN0IGdvIGFsb25nIHRoZSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBlZGdlcyBvZiB0aGUgZ3JpZCAoc2VlIGd1cmUpLCBhbmQgdGhlIHR3byB3aXJlcyBtYXkgbm90IHNoYXJlIGEgY29tbW9uIHZlcnRleC4gRGV0ZXJtaW5lIHRoZSBtaW5pbXVtIGxlbmd0aCBvZiB3aXJlIG5lZWRlZCB0byBkbyBzby4gVGhlIHdpcmUgbWF5IG5vdCBnbyBvdXRzaWRlIHRoZSBjaXJjdWl0IGJvYXJkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzLCBOICgyICZsZTsgTiAmbGU7IDEwMCkgYW5kIE0gKDIgJmxlOyBNICZsZTsgMTAwKSwgdGhlIGdyaWQgc2l6ZSBvZiB0aGUgY2lyY3VpdCBib2FyZC48XC9wPlxyXG5cclxuPHA+VGhlbiBmb2xsb3dzIGZvdXIgbGluZXMgY29udGFpbmluZyB0aGUgY29vcmRpbmF0ZXMgZm9yIHRoZSBwb2ludHMgQTEsIEEyLCBCMSBhbmQgQjIsIHJlc3BlY3RpdmVseS4gRWFjaCBjb29yZGluYXRlIHBhaXIgd2lsbCBiZSBkZXNjcmliZWQgdXNpbmcgdHdvIGludGVnZXJzIGFuZCB3aWxsIGNvcnJlc3BvbmQgdG8gYW4gaW50ZXJzZWN0aW9uIHBvaW50IGluIHRoZSBncmlkLiBUaGUgcnN0IGNvb3JkaW5hdGUgd2lsbCBiZSBiZXR3ZWVuIDAgYW5kIE4gaW5jbHVzaXZlIGFuZCB0aGUgc2Vjb25kIGNvb3JkaW5hdGUgYmV0d2VlbiAwIGFuZCBNIGluY2x1c2l2ZS4gQWxsIGNvb3JkaW5hdGUgcGFpcnMgd2lsbCBiZSB1bmlxdWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIGxlbmd0aCBvZiB3aXJlIG5lZWRlZCB0byBjb25uZWN0IHRoZSBwb2ludHMsIG9yICZxdW90O0lNUE9TU0lCTEUmcXVvdDsgaWYgaXQmIzM5O3Mgbm90IHBvc3NpYmxlIHRvIGRvIHNvLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d