ხეივანი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, VII-VIII


ქალაქის ერთ-ერთ პარკს დიდი ხანია სათანადო ყურადღება აღარ მიქცევია და ამიტომ მასში თითქმის ყველა სასეირნო ბილიკი განადგურებულია. შესაბამისად, ქალაქის მესვეურებმა მისი რეაბილიტაცია გადაწყვიტეს. პარკი n მეტრი სიგრძის გვერდის მქონე კვადრატის ფორმისაა, შემოღობილია მესრით და აქვს ზუსტად ორი ჭიშკარი. დიზაინერებმა პირველ რიგში გააკეთეს პარკის სქემა, რომელზედაც იგი დაყოფილია nxn რაოდენობის ზონად (თითოეული ზონა წარმოადგენს 1 მეტრი სიგრძის გვერდის მქონე კვადრატს). შესაბამისად, პარკის სქემა გამოიყურება, როგორც კვადრატული მატრიცა n რაოდენობის სტრიქონითა და  n რაოდენობის სვეტით. სტრიქონები და სვეტები გადანომრილია 1-დან n-მდე და მატრიცის თითოეული ელემენტი ერთეულოვან კვადრატს შეესაბამება. ყოველ ასეთ ზონაში შეიძლება დარგული იყოს ხე ან იგი იყოს თავისუფალი.

ქალაქის მესვეურებს სურთ პარკის თავისუფალ ზონებში დააგონ 1 2 ფართობის მქონე ფილების მინიმალური რაოდენობა ისე, რომ მიიღონ უწყვეტგზიანი ხეივანი ერთი ჭიშკრიდან მეორემდე.

დაწერეთ პროგრამა, რომელიც დაადგენს ფილების იმ მინიმალურ რაოდენობას, რომელიც საჭიროა ერთი ჭიშკრიდან მეორემდე მიმავალი უწყვეტი გზის დასაგებად.

შესატანი მონაცემები: სტანდრატული შეტანის პირველ  სტრიქონში მოცემულია ორი მთელი დადებითი n და m  რიცხვი (1 ≤ n ≤ 175, 1 ≤ m < n*n) პარკის ზომა და მასში ხეების რაოდენობა შესაბამისად. მომდევნო m რაოდენობის სტრიქონიდან თითოეულში ჩაწერილია ასევე ორი მთელი დადებითი x და y რიცხვი -  შესაბამისი ხის კოორდინატები (x სტრიქონის ნომერია, ხოლო y კისვეტის). ფაილის ბოლო სტრიქონი შეიცავს ოთხ მთელ დადებით რიცხვს: x1, y1, x2, y2, სადაც x1 და y1 იმ ზონის კოორდინატებია, რომელშიც პირველი ჭიშკარია განთავსებული, ხოლო x2 და y2 კი იმ ზონისა, სადაც მეორე ჭიშკარია.

ყველა სტრიქონში მონაცემები ერთმანეთისაგან თითო ჰარითაა გამოყოფილი.

გამოსატანი მონაცემები სტანდარტული გამოტანის ერთადერთ სტრიქონში უნდა ჩაიწეროს უწყვეტი გზის დასაგებად საჭირო ფილების მინიმალური რაოდენობა.

 შეზღუდვები:

ხეივანი უწყვეტია, თუ ნებისმიერ ორ მეზობელ ფილას საერთო გვერდი აქვს;

ხეივანი იწყება ზონიდან, რომელშიც პირველი ჭიშკარია განთავსებული და მთავრდება ზონაში, რომელშიც მეორე ჭიშკარია განთავსებული;

ჭიშკრების პოზიციები განსხვავებულია და ისინი თავისუფალ ზონებშია განთავსებული;

•              გარანტირებულია, რომ ყოველი ტესტისათვის არსებობს ამოცანის ამონახსნი.




მაგალითები

შესატანი მონაცემები
8 6 2 7 3 3 4 6 5 4 7 3 7 5 1 1 8 8 დაკოპირება
გამოსატანი მონაცემები
15 დაკოპირება

შენიშვნა

ფილათა მინიმალური რაოდენობით დაგებული ერთ-ერთი შესაძლო გზა:

OOO-----

--OO--x-

--xO----

---OOx--

---xO---

----OO--

--x-xOO-

------OO

„x”-ით აღნიშნულია ხე, „-”-თი თავისუფალი ზონა, ხოლოO”-თი კიფილა.