堡垒

时间限制:10s      空间限制:128MB

题目描述

有个国家,它的所有城市如下图被公路连成了一个环,依次编号为1..N。并且在这个环内有一些笔直的公路,每条公路连接两个城市。为了不发生交通事故,任意两条公路不会在中途相交。为了使城市之间的交通更便利,城市间会建尽可能多的公路,但两个城市之间最多建一条公路。
    现在因为有另一个国家想破坏这个国家的交通系统,所以我们需要在一些城市建堡垒,使每条公路都能被监督(在i城市建堡垒可以监督与i城市相邻的公路)。问你最少需要建多少个堡垒。


输入格式

第一行有一个正整数N,表示城市数。
接下来2*N-3行(环上有N条公路,环中有N-3条公路),每行两个正整数uv,表示城市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<=1000。
100%的数据中:N<=100000。


题目来源

没有写明来源

Menuappsclose