D2 - Dual Friendship [Hard]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

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

問題文

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

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

  • ss と人 uu とが互いに友達である
  • tt と人 uu とが互いに友達である

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

  • 1p<qN1 \leq p < q \leq N
  • 1rN1 \leq r \leq N
  • pp と人 qq とが人 rr を介して友達の友達である

制約

  • 1N2×1051 \leq N \leq \bold{2 \times 10^5}
  • 0Mmin{N(N1)2,2×105}0 \leq M \leq \mathrm{min}\, \{\, \frac{N(N-1)}{2},\, \bold{2 \times 10^5} \,\}
  • 1ai<biN(1iN)1 \leq a_i < b_i \leq N \scriptsize \hspace{0.4em} (1 \leq i \leq N)
  • iji\neq j ならば (ai,bi)(aj,bj)(a_i, b_i)\neq(a_j, b_j)
  • 入力はすべて整数である

サンプル

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

入力例1
4 3
1 2
2 3
2 4
出力例1
3

入力例1_友好関係
(p,q,r)=(1,3,2),(1,4,2),(3,4,2)(p, q, r) = (1, 3, 2), (1, 4, 2), (3, 4, 2) のときに条件を満たします.


入力例2
4 4
1 2
2 3
2 4
1 3
出力例2
5

入力例2 友好関係
(p,q,r)=(1,2,3),(1,3,2),(1,4,2),(2,3,1),(3,4,2)(p, q, r) = (1, 2, 3), (1, 3, 2), (1, 4, 2), (2, 3, 1), (3, 4, 2) のときに条件を満たします.


入力例3
4 5
1 2
2 3
2 4
1 3
3 4
出力例3
8

入力例3 友好関係
(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)(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) のときに条件を満たします.

Submit


Go (1.21)