← 返回题目列表

Codeforces · 1302/B

B. 有向无环图

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

这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543

给定一个有向无环图 $$$G$$$,其中包含 $$$n$$$ 个顶点和 $$$m$$$ 条边。用 $$$R(v)$$$ 表示通过沿 $$$G$$$ 的边移动可从 $$$v$$$ 到达的所有顶点 $$$u$$$ 的集合。求 $$$\sum\limits_{v=1}^n |R(v)|^2$$$。

输入

第一行包含两个整数 $$$n, m$$$ ($$$1 \leq n, m \leq 5 \cdot 10^4$$$) 表示 $$$G$$$ 的顶点数和边数。

接下来的 $$$m$$$ 行包含两个整数 $$$u, v$$$ ($$$1 \leq u \neq v \leq n$$$),表示从 $$$u$$$ 到 $$$v$$$ 的边。

保证给定的图不包含任何循环。

输出

打印一个整数——问题的答案。

示例

输入 #1

5 4
1 2
2 3
3 4
4 5

输出 #1

55

输入 #2

12 6
1 2
3 4
5 6
8 7
10 9
12 11

输出 #2

30

输入 #3

7 6
1 2
1 3
2 4
2 5
3 6
3 7

输出 #3

45