Магический замок

시간 제한2초메모리 제한1024 MB

요약

볼록 다각형의 삼각분할이 현 목록으로 주어질 때, 모든 삼각형이 사라지도록 제거해야 하는 현의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디, 트리, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

Оказалось, что замок представляет собой правильный многоугольник, состоящий из $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$ ).

출력

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

힌트

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

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

예제2

예제 1
입력
```
6
2 4
2 5
2 6
```
예상 출력
```
2
```
예제 2
입력
```
6
2 4
2 6
6 4
```
예상 출력
```
3
```