시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB123350.000%

문제

Долгие поиски привели Ньюта Саламандера к тайному логову Грин-де-Вальда, в котором он хранит все свои секреты. Юный маг не удивился, увидев на входе в логово сложный магический замок, защищенный заклинанием. Но в логово ему нужно попасть любой ценой, поэтому Ньют начал изучать наложенное на замок заклинание.

Оказалось, что замок представляет собой правильный многоугольник, состоящий из $n$ вершин, пронумерованных по часовой стрелке. Заклинание, наложенное на замок, состоит из $n - 3$ магических связей, которые триангулируют многоугольник --- разбивают его на $n - 2$ треугольника с вершинами в вершинах многоугольника, попарно не пересекающихся между собой и полностью покрывающих многоугольник. Например, на правильный шестиугольник магические связи могут быть наложены одним из следующих способов:

Также Ньют понял, что замок не просто так был разбит магическими связями именно на треугольники --- такие магические связи считаются самыми прочными. Поэтому, чтобы заклинание можно было разрушить, Саламандеру сначала придется разрушить все треугольники. К счастью, с помощью заклинания <<Риктусемпра>> за один раз юный маг может разрушить одну магическую связь, соединяющую две вершины многоугольника. Так как времени у Саламандера немного и вскоре наверняка сработает защитное заклинание, навсегда закрывающее вход в логово, он хочет узнать, какое минимальное количество раз надо применить заклинание <<Риктусемпра>>, чтобы разрушить все треугольники на магическом замке. Помогите ему!

입력

В первой строке содержится число $n$ --- количество вершин правильного многоугольника ($4 \le n \le 10^5$).

В $i$-й из следующих $n-3$ строк через пробел содержится два числа $a_i$ и $b_i$ --- номера вершин многоугольника, соединенных магической связью. Гарантируется, что все $n-3$ магические связи образуют триангуляцию многоугольника, то есть разбивают его на треугольники с вершинами в вершинах данного правильного $n$-угольника ($1 \le a_i, b_i \le n$).

출력

В единственной строке выведите минимальное количество заклинаний <<Риктусемпра>>, которые надо применить, чтобы разрушить все треугольники в магическом замке.

예제 입력 1

6
2 4
2 5
2 6

예제 출력 1

2

예제 입력 2

6
2 4
2 6
6 4

예제 출력 2

3

노트

В первом примере достаточно разрушить магические связи, соединяющие вершины $(2, 4)$ и $(2, 6)$.

Во втором примере придется разрушить все три магические связи.