Language: C++

#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

typedef tuple<int, int, int> state; // now, from, clr
typedef tuple<int, int> cond; // now, depth

int N;
int M;
vector<int> V[100010];

int main () {
  cin >> N >> M;
  for (auto i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    V[a].push_back(b);
    V[b].push_back(a);
  }
  for (auto i = 0; i < N; ++i) {
    random_shuffle(V[i].begin(), V[i].end());
  }
  int visited[100010];
  fill(visited, visited+100010, 0);
  int color[100010];
  fill(color, color+100010, 0);
  int parent[100010];
  stack<state> S;
  S.push(state(0, -1, 1));
  while (!S.empty()) {
    int now = get<0>(S.top());
    int from = get<1>(S.top());
    int clr = get<2>(S.top());
    // cerr << "now = " << now << ", from = " << from << endl;
    S.pop();
    if (visited[now] == 0) {
      visited[now] = true;
      parent[now] = from;
      color[now] = clr;
      // cerr << "parent[" << now << "] = " << from << endl;
      S.push(state(now, now));
      for (auto x : V[now]) {
        if (x != parent[now]) {
          S.push(state(x, now, 3-clr));
        }
      }
    } else if (visited[now] == 1) {
      if (from != now) {
        if (color[now] == 3) continue;
        if (color[now] == clr) continue;
        color[now] = 3;
        for (auto x : V[now]) {
          if (x != parent[now]) {
            S.push(state(x, now, 3-clr));
          }          
        }
      } else {
        visited[now] = 2;
      }
    }
  }
  for (auto i = 0; i < 100010; ++i) {
    visited[i] = (color[i] == 3);
  }
  ll ans = 0;
  for (auto i = 0; i < N; ++i) {
    if (visited[i]) continue;
    stack<cond> SS;
    SS.push(cond(i, 0));
    ll cnt[2] = {0, 0};
    while (!SS.empty()) {
      int now = get<0>(SS.top());
      int depth = get<1>(SS.top());
      SS.pop();
      if (!visited[now]) {
        visited[now] = true;
        cnt[depth%2]++;
        for (auto x : V[now]) {
          if (!visited[x]) {
            SS.push(cond(x, depth+1));
          }
        }
      }
    }
    ans += cnt[0] * cnt[1];
  }
  ll L = 0;
  for (auto i = 0; i < N; ++i) {
    if (color[i] == 3) L++;
  }
  cerr << "L = " << L << endl;
  ans += L * (L-1) / 2 + L * (N-L) - M;
  cout << ans << endl;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:51:19: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   51 |     random_shuffle(V[i].begin(), V[i].end());
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_algo.h:4492:5: note: declared here
 4492 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~
a.cc:71:28: error: no matching function for call to 'std::tuple<int, int, int>::tuple(int&, int&)'
   71 |       S.push(state(now, now));
      |                            ^
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/tuple:1646:9: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Args2 ...>&&) [with _UElements = _Alloc; bool _Valid = {_UElements ...}; typename std::enable_if<_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> = _Valid; _Elements = {int, int, int}]'
 1646 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |         ^~~~~
/usr/include/c++/14/tuple:1646:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/tuple:1634:9: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Args2 ...>&&) [with _UElements = _Alloc; bool _Valid = {_UElements ...}; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = _Valid; _Elements = {int, int, int}]'
 1634 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |         ^~~~~
/usr/include/c++/14/tuple:1634:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/tuple:1623:9: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Args2 ...>&) [with _UElements = _Alloc; bool _Valid = {_UElements ...}; typename std::enable_if<_TCC<_Valid>::__is_explicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> = _Valid; _Elements = {int, int, int}]'
 1623 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |         ^~~~~
/usr/include/c++/14/tuple:1623:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/tuple:1611:9: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_implicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Args2 ...>&) [with _UElements = _Alloc; bool _Valid = {_UElements ...}; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> = _Valid; _Elements = {int, int, int}]'
 1611 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |         ^~~~~
/usr/include/c++/14/tuple:1611:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/tuple:1603:9: note: candidate: 'template<class _Alloc> std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, std::tuple< <template-parameter-1-1> >&&) [with _Elements = {int, int, int}]'
 1603 |         tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
      |         ^~~~~
/usr/include/c++/14/tuple:1603:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/tuple:1598:9: note: candidate: 'template<class _Alloc> std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple< <template-parameter-1-1> >&) [with _Elements = {int, int, int}]'
 1598 |         tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
      |         ^~~~~
/usr/include/c++/14/tuple:1598:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/tuple:1591:9: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, _UElements&& ...) [with _UElements = _Alloc; bool _Valid = {_UElements ...}; typename std::enable_if<_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> = _Valid; _Elements = {int, int, int}]'
 1591 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |         ^~~~~
/usr/include/c++/14/tuple:1591:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/tuple:1587:59: error: no matching function for call to 'std::tuple<int, int, int>::__valid_args<>()'
 1587 |                  bool _Valid = __valid_args<_UElements...>(),
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/tuple:1390:31: note: candidate: 'template<class _Up> static constexpr bool std::tuple< <template-parameter-1-1> >::__valid_args() [with _Elements = {int, int, int}]'
 1390 |         static constexpr bool __valid_args()
      |                               ^~~~~~~~~~~~
/usr/include/c++/14/tuple:1390:31: note:   template argument deduction/substitution failed:
/usr/include/c++/14/tuple:1587:59: note:   couldn't deduce template parameter '_Up'
 1587 |                  bool _Valid = __valid_args<_UElements...>(),
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/tuple:1398:31: note: candidate: 'template<class, class, class ... _Tail> static constexpr bool std::tuple< <template-parameter-1-1> >::__valid_args() [with _Tail = <template-parameter-1-1>; _Elements = {int, int, int}]'
 1398 |         static constexpr bool __valid_args()
      |                               ^~~~~~~~~~~~
/usr/include/c++/14/tuple:1398:31: note:   template argument deduction/substitution failed:
/usr/include/c++/14/tuple:1587:59: note:   couldn't deduce template parameter '<template-parameter-1-1>'
 1587 |                  bool _Valid = __valid_args<_UElements...>(),
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/tuple:1581:9: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, _UElements&& ...) [with _UElements = _Alloc; bool _Valid = {_UElements ...}; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = _Valid; _Elements = {int, int, int}]'
 1581 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |         ^~~~~
/usr/include/c++/14/tuple:1581:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/tuple:1578:57: error: no matching function for call to 'std::tuple<int, int, int>::__valid_args<>()'
 1578 |                bool _Valid = __valid_args<_UElements...>(),
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/tuple:1390:31: note: candidate: 'template<class _Up> static constexpr bool std::tuple< <template-parameter-1-1> >::__valid_args() [with _Elements = {int, int, int}]'
 1390 |         static constexpr bool __valid_args()
      |                               ^~~~~~~~~~~~
/usr/include/c++/14/tuple:1390:31: note:   template argument deduction/substitution failed:
/usr/include/c++/14/tuple:1578:57: note:   couldn't deduce template parameter '_Up'
 1578 |                bool _Valid = __valid_args<_UElements...>(),
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/tuple:1398:31: note: candidate: 'template<class, class, class ... _Tail> static constexpr bool std::tuple< <template-parameter-1-1> >::__valid_args() [with _Tail = <template-parameter-1-1>; _Elements = {int, int, int}]'
 1398 |         static constexpr bool __valid_args()
      |                               ^~~~~~~~~~~~
/usr/include/c++/14/tuple:1398:31: note:   template argument deduction/substitution failed:
/usr/include/c++/14/tuple:1578:57: note:   couldn't deduce template parameter '<template-parameter-1-1>'
 1578 |                bool _Valid = __valid_args<_UElements...>(),
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/tuple:1573:9: note: candidate: 'template<class _Alloc, bool _NotEmpty, typename std::enable_if<std::tuple<int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<const int&, const int&, const int&>(), bool>::type <anonymous> > std::tuple< <template-parameter-1-1> >::tuple(std::allocator_arg_t, const _Alloc&, const _Elements& ...) [with bool _NotEmpty = _Alloc; typename std::enable_if<_TCC<_Valid>::__is_explicitly_constructible<const _Elements& ...>(), bool>::type <anonymous> = _NotEmpty; _Elements = {int, int, int}]'
 1573 |         tuple(allocator_arg_t __tag, const _Alloc& __a,
      |