問題 D1 とは制約と内容が異なります

問題文

D1 - Dual Friendship [Easy] と同じ状況を考えます

新たに，「人 $s$ と人 $t$ とが人 $u$ を介して友達の友達である」とは $3$ 整数 $s, t, u \scriptsize \hspace{0.3em} (1 \leq s, t,u \leq N)$ が下記の条件を満たすことを指します．

• 人 $s$ と人 $u$ とが互いに友達である
• 人 $t$ と人 $u$ とが互いに友達である

下記の条件をすべて満たす正整数の組 $(p, q, r)$ は何通りあるか，求めてください．

• $1 \leq p < q \leq N$
• $1 \leq r \leq N$
• 人 $p$ と人 $q$ とが人 $r$ を介して友達の友達である

制約

• $1 \leq N \leq \bold{2 \times 10^5}$
• $0 \leq M \leq \mathrm{min}\, \{\, \frac{N(N-1)}{2},\, \bold{2 \times 10^5} \,\}$
• $1 \leq a_i < b_i \leq N \scriptsize \hspace{0.4em} (1 \leq i \leq N)$
• $i\neq j$ ならば $(a_i, b_i)\neq(a_j, b_j)$
• 入力はすべて整数である

サンプル

入力は D1 と同一のものです．

4 3
1 2
2 3
2 4

3

$(p, q, r) = (1, 3, 2), (1, 4, 2), (3, 4, 2)$ のときに条件を満たします．

4 4
1 2
2 3
2 4
1 3

5

$(p, q, r) = (1, 2, 3), (1, 3, 2), (1, 4, 2), (2, 3, 1), (3, 4, 2)$ のときに条件を満たします．

4 5
1 2
2 3
2 4
1 3
3 4

8

$(p, q, r) = (1, 2, 3), (1, 3, 2), (1, 4, 2), (1, 4, 3), (2, 3, 1), (2, 3, 4), (2, 4, 3), (3, 4, 2)$ のときに条件を満たします．