题目描述

有个国家，它的所有城市如下图被公路连成了一个环，依次编号为 $1\dots N$。并且在这个环内有一些笔直的公路，每条公路连接两个城市。为了不发生交通事故，任意两条公路不会在中途相交。为了使城市之间的交通更便利，城市间会建尽可能多的公路，但两个城市之间最多建一条公路。

现在因为有另一个国家想破坏这个国家的交通系统，所以我们需要在一些城市建堡垒，使每条公路都能被监督（在 $i$ 城市建堡垒可以监督与 $i$ 城市相邻的公路）。问你最少需要建多少个堡垒。

输入格式

第一行有一个正整数 $N$，表示城市数。 接下来 $2\times (N-3)$ 行，每行两个正整数 $u, v$，表示城市 $u$ 与城市 $v$ 之间有一条公路。

输出格式

仅有一行一个正整数，表示最少的堡垒数。

输入样例

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 3
8 3
7 3
7 5
5 3

输出样例

4

提示

在 $1,3,5,7$ 号城市建堡垒即可。

数据规模

对于 $30\%$ 的数据中：$N \leq 1000$。 对于 $100\%$ 的数据中：$N \leq 100000$。