Farmer John החליט לתת לכל פרה טלפון לעידוד קשרים חברתיים. צריך אנטנות ב־$N$ שטחי המרעה ($1 \le N \le 10,000$), ממוספרים $1,\ldots,N$, כדי שכולן יתקשרו.

בדיוק $N-1$ זוגות סמוכים; לכל $A$, $B$ ($1 \le A \le N; 1 \le B \le N; A \ne B$) יש רצף שטחים סמוכים שמתחיל ב־$A$ ומסתיים ב־$B$. אנטנות רק בשטחי המרעה, וכל אחת מכסה את שלה ואת כל השטחים הסמוכים.

מצאו את מינימום האנטנות לכיסוי כל שטח.

קלט

קראו מהקלט התקני.

• שורה 1: השלם $N$.
• שורות $2,\ldots,N$: זוג סמוך, השלמים $A$, $B$ מופרדים ברווח.

פלט

כתבו לפלט התקני.

• שורה 1: שלם, מינימום האנטנות.

דוגמאות

קלט 1

5
1 3
5 2
4 3
3 5

פלט 1

2

הערה

5 שטחים: 1 ו־3, 5 ו־2, 4 ו־3, 3 ו־5 סמוכים. גאומטרית החווה נראית כך (או באופן דומה):

               4  2
               |  |
            1--3--5

אפשר להציב ב־2 ו־3 או ב־3 ו־5.

מחבר הבעיה: Jeffrey Wang, 2007