Score : $300$ points

问题陈述

在AtCoder共和国中，有$N$个城市，编号从1到$N$，以及$M$条道路，编号从1到$M$。

第$i$条道路从城市$A_i$通向城市$B_i$，但你不能通过它从城市$B_i$到达城市$A_i$。

Puma正在计划她的旅程，她将从某个城市出发，沿着零条或多条道路行进，并最终抵达某个城市。

Puma的旅程可能有多少对起始城市和目的地城市组合？我们需区分具有相同城市集合但顺序不同的对。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$.

Road $i$ leads from City $A_i$ to City $B_i$, but you cannot use it to get from City $B_i$ to City $A_i$.

Puma is planning her journey where she starts at some city, travels along zero or more roads, and finishes at some city.

How many pairs of cities can be the origin and destination of Puma's journey? We distinguish pairs with the same set of cities in different orders.

Constraints

• $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.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

Output

Print the answer.

Sample Input 1

3 3
1 2
2 3
3 2

Sample Output 1

7

We have seven pairs of cities that can be the origin and destination: $(1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)$.

Sample Input 2

3 0

Sample Output 2

3

We have three pairs of cities that can be the origin and destination: $(1,1),(2,2),(3,3)$.

Sample Input 3

4 4
1 2
2 3
3 4
4 1

Sample Output 3

16

Every pair of cities can be the origin and destination.

update @ 2024/3/10 09:17:13