AT_abc282_d [ABC282D] Make Bipartite 2

[problemUrl]: https://atcoder.jp/contests/abc282/tasks/abc282_d $ N $ 個の頂点と $ M $ 本の辺からなる単純な（すなわち、自己ループも多重辺も含まない）無向グラフ $ G $ が与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結びます。 $ 1\ \leq\ u\ \lt\ v\ \leq\ N $ を満たす整数の組 $ (u,\ v) $ であって、下記の $ 2 $ つの条件をともに満たすものの個数を出力してください。 - グラフ $ G $ において、頂点 $ u $ と頂点 $ v $ を結ぶ辺は存在しない。 - グラフ $ G $ に、頂点 $ u $ と頂点 $ v $ を結ぶ辺を追加して得られるグラフは、二部グラフである。 二部グラフとは？無向グラフが**二部グラフ**であるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。 - 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ \min\ \lbrace\ 2\ \times\ 10^5,\ N(N-1)/2\ \rbrace $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - グラフ $ G $ は単純 - 入力はすべて整数 ### Sample Explanation 1 問題文中の条件を満たす整数の組 $ (u,\ v) $ は、$ (1,\ 4) $ と $ (1,\ 5) $ の $ 2 $ つです。よって、$ 2 $ を出力します。 他の組については、例えば、$ (1,\ 3) $ はグラフ $ G $ において頂点 $ 1 $ と頂点 $ 3 $ を結ぶ辺が存在することから、 $ (4,\ 5) $ はグラフ $ G $ に頂点 $ 4 $ と頂点 $ 5 $ を結ぶ辺を追加して得られるグラフが二部グラフではないことから、 それぞれ問題文中の条件を満たしません。 ### Sample Explanation 2 与えられるグラフが二部グラフであったり連結であるとは限らないことに注意してください。