| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 12 | 3 | 3 | 50.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$).
В единственной строке выведите минимальное количество заклинаний <<Риктусемпра>>, которые надо применить, чтобы разрушить все треугольники в магическом замке.
6 2 4 2 5 2 6
2
6 2 4 2 6 6 4
3
В первом примере достаточно разрушить магические связи, соединяющие вершины $(2, 4)$ и $(2, 6)$.
Во втором примере придется разрушить все три магические связи.