配点 : $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$

出力

答えを出力せよ。

3 3
1 2
2 3
3 2

7

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

3 0

3

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

4 4
1 2
2 3
3 4
4 1

16

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