ينص قانون Moore على أن عدد الترانزستورات على الشريحة يتضاعف كل عامين. والمدهش أن هذا القانون ظل صحيحًا لأكثر من نصف قرن. كلما لم تعد التقنية الحالية تسمح بمزيد من النمو، ابتكر الباحثون تقنيات تصنيع جديدة لحشد الدوائر بكثافة أعلى. في المستقبل القريب، قد يعني هذا إنشاء شرائح ثلاثية الأبعاد بدلًا من ثنائية الأبعاد. لكن بُعدين يكفيان لهذه المسألة.

من المشكلات المشتركة في جميع تصاميم العتاد ثنائية الأبعاد (مثل الشرائح وبطاقات الرسوميات واللوحات الأم وغيرها) وضع الأسلاك. عند تمديد الأسلاك على العتاد، تنشأ مشكلة إذا كان لا بد أن تتقاطع. وعند حدوث تقاطع، يجب استخدام تجهيزات خاصة للسماح لسلكين كهربائيين بالمرور أحدهما فوق الآخر، مما يجعل التصنيع أكثر تكلفة.

مسألتنا هي الآتية: يُعطى لك تصميم عتاد وُضعت فيه عدة أسلاك بالفعل (كلها قطع مستقيمة). كما تُعطى نقطتا البداية والنهاية لوصلة سلكية جديدة يراد إضافتها. عليك تحديد أقل عدد من الأسلاك الموجودة التي يجب عبورها لربط نقطتي البداية والنهاية. لا يلزم أن تكون هذه الوصلة خطًا مستقيمًا. الشرط الوحيد هو ألا تعبر عند نقطة يلتقي أو يتقاطع فيها سلكان موجودان أو أكثر بالفعل.

الشكل L.1: مثال الإدخال الأول.

يوضح الشكل L.1 مثال الإدخال الأول. تشكل ثمانية أسلاك موجودة خمسة مربعات. تقع نقطتا البداية والنهاية للوصلة الجديدة في المربع الأقصى يسارًا والأقصى يمينًا، على الترتيب. يبين الخط الأسود المتقطع أن التوصيل المباشر سيعبر أربعة أسلاك، بينما يعبر الحل الأمثل سلكين فقط (المنحنى الأزرق).

الإدخال

يتكون الإدخال من حالة اختبار واحدة. يحتوي السطر الأول على خمسة أعداد صحيحة $m,x_0,y_0,x_1,y_1$، تمثل عدد الأسلاك الموجودة ($m \le 100$) ونقطتي البداية والنهاية المطلوب ربطهما. يلي ذلك $m$ سطرًا، يحتوي كل منها على أربعة أعداد صحيحة $x_a,y_a,x_b,y_b$ تصف سلكًا موجودًا ذا طول غير صفري من $(x_a,y_a)$ إلى $(x_b,y_b)$. القيمة المطلقة لكل إحداثي في الإدخال أقل من $10^5$. لكل زوج من الأسلاك نقطة مشتركة واحدة على الأكثر، أي إن الأسلاك لا تتراكب. لا تقع نقطتا البداية والنهاية للسلك الجديد على أي سلك موجود.

الإخراج

اعرض أقل عدد من الأسلاك التي يجب عبورها لربط نقطتي البداية والنهاية.

أمثلة

الإدخال 1

8 3 3 19 3
0 1 22 1
0 5 22 5
1 0 1 6
5 0 5 6
9 0 9 6
13 0 13 6
17 0 17 6
21 0 21 6

الإخراج 1

2

الإدخال 2

1 0 5 10 5
0 0 10 10

الإخراج 2

0