Tour

题目描述

阿托德尔共和国有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。 道路 $i$ 从城市 $A_i$ 通向城市 $B_i$，但不能用于从城市 $B_i$ 到城市 $A_i$。 Puma 正在规划她的旅程，她从某个城市出发，沿着零条或多条道路行驶，最后到达某个城市。 有多少对城市可以作为 Puma 旅程的起点和终点？我们把相同两个城市但顺序不同的对视为不同的对。

输入格式

输入按如下格式从标准输入给出： $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

输出答案。

3 3
1 2
2 3
3 2

7

3 0

3

4 4
1 2
2 3
3 4
4 1

16

提示

$2 \leq N \leq 2000$ $0 \leq M \leq \min(2000,N(N-1))$ $1 \leq A_i,B_i \leq N$ $A_i \neq B_i$ $(A_i,B_i)$ are distinct. 输入中的所有值均为整数。我们有七对可以作为起点和终点的城市：$(1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)$.
我们有三对可以作为起点和终点的城市：$(1,1),(2,2),(3,3)$.
每一对城市都可以作为起点和终点。

标签: AtCoder|abc204C

来源

AtCoder|abc204C