← 返回题目列表

Codeforces · 958/B1

B1. 最大控制(简单)

中文机器翻译题面 查看原题

抵抗组织正试图控制特定太阳系中的所有行星。这个太阳系的形状像一棵树。更准确地说,一些行星通过双向超空间隧道连接,每对行星之间都有一条路径,但移除任何隧道都会断开其中一些行星的连接。

抵抗组织已经采取措施,在适当的时候,使他们能够控制每一个并不遥远的星球。如果一颗行星仅通过单个超空间隧道与其他行星相连,则该行星被认为是遥远的。

还有多少工作要做:也就是说,还有多少个遥远的行星?

输入

输入的第一行包含一个整数 N (2 ≤ N ≤ 1000) – 星系中行星的数量。

接下来的 N - 1 行描述了行星之间的超空间隧道。 N - 1 行中的每一行包含两个空间分隔的整数 u 和 v (1 ≤ u, v ≤ N),表示行星 u 和 v 之间存在双向超空间隧道。保证每两个行星都由一条隧道路径连接,并且每条隧道连接不同的一对行星。

输出

表示远程行星数量的单个整数。

示例

输入 #1

5
4 1
4 2
1 3
1 5

输出 #1

3

输入 #2

4
1 2
4 3
1 4

输出 #2

2

注意

在第一个示例中,仅行星 2、3 和 5 通过单个隧道连接。

在第二个示例中,远程行星是 2 和 3。

请注意,这个问题只有两个版本——简单和中等。