← 返回题目列表

Codeforces · 690/F1

F1. 生命之树(简单)

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

海蒂终于找到了神秘的生命之树 - 一种传奇的组合结构,据说其中包含击败不死军队所必需的预言。

从表面上看,生命之树只是计算机科学中众所周知的常规无向树。这意味着它是 n 个点(称为顶点)的集合,其中一些点使用 n - 1 条线段(边)连接,以便每对顶点通过一条路径(一条或多条边的序列)连接。

为了破译预言,海蒂需要执行许多步骤。第一个是计算树中生命线的数量——这些是长度为 2 的路径,即由两条边组成。帮助她!

输入

输入的第一行包含一个整数 n – 树中的顶点数 (1 ≤ n ≤ 10000)。顶点标有从 1 到 n 的数字。然后是 n - 1 行,每行使用两个空格分隔的数字 a b 描述一条边,即由边连接的顶点的标签 (1 ≤ a < b ≤ n)。保证输入代表一棵树。

输出

打印一个整数——树中生命线的数量。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

3

输入 #2

5
1 2
2 3
3 4
3 5

输出 #2

4

注意

在第二个示例中,有四个生命线:顶点 1 和 3、2 和 4、2 和 5 以及 4 和 5 之间的路径。