חוק 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