C - Tour Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。

道路 i を通ると都市 A_i から B_i へ移動することができます。都市 B_i から都市 A_i への通行はできません。

ピューマは、どこかの都市からスタートし、0 本以上の道路を使い移動して、どこかの都市をゴールとするような旅行の計画を立てようとしています。

スタート地点とゴール地点の都市の組として考えられるものは何通りありますか?

制約

  • 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) は相異なる
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
\vdots
A_M B_M

出力

答えを出力せよ。


入力例 1

3 3
1 2
2 3
3 2

出力例 1

7

スタート地点とゴール地点の組として考えられるものは (1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)7 通りです。


入力例 2

3 0

出力例 2

3

スタート地点とゴール地点の組として考えられるものは (1,1),(2,2),(3,3)3 通りです。


入力例 3

4 4
1 2
2 3
3 4
4 1

出力例 3

16

スタート地点とゴール地点の組として全ての都市の組み合わせが可能です。

Score : 300 points

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.