抵抗组织正试图控制特定太阳系中的所有行星。这个太阳系的形状像一棵树。更准确地说,一些行星通过双向超空间隧道连接,每对行星之间都有一条路径,但移除任何隧道都会断开其中一些行星的连接。
抵抗组织已经采取措施,在适当的时候,使他们能够控制每一个并不遥远的星球。如果一颗行星仅通过单个超空间隧道与其他行星相连,则该行星被认为是遥远的。
还有多少工作要做:也就是说,还有多少个遥远的行星?
输入
输入的第一行包含一个整数 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。
请注意,这个问题只有两个版本——简单和中等。