題目描述:

網(wǎng)絡安全一直是非常重要的一件事情，現(xiàn)在太空觀測基地里的機房所有主機都用網(wǎng)線相連，如圖所示，主機編號為1..N。在這個環(huán)內(nèi)有一些額外的網(wǎng)線直接連接兩臺主機。為了機房網(wǎng)線布線合理，任意兩條網(wǎng)線中途不能相交。為了使主機之間的網(wǎng)絡更加通暢，主機之間會盡可能的相連，但兩臺主機之間最多連接一條網(wǎng)線。

現(xiàn)在想測試這個機房網(wǎng)絡系統(tǒng)的安全性能，需要在一些主機上安裝監(jiān)測軟件，使每條網(wǎng)線都能被檢測（在第i號主機安裝監(jiān)測軟件可以監(jiān)測與它直接相連的網(wǎng)線）。請問最少需要在多少臺主機上安裝監(jiān)測軟件。

輸入說明:

第一行有一個正整數(shù)N（N<=100000），表示主機數(shù)。接下來2*N-3行（環(huán)上有N臺主機，環(huán)內(nèi)有N-3條網(wǎng)線），每行兩個正整數(shù)u、v，表示主機u與主機v之間有一條網(wǎng)線。

輸出說明:

一個正整數(shù)，表示最少的安裝監(jiān)測軟件的主機數(shù)目。

輸入樣例:

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