Language: C++

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, m, E, O, h[N], par[N], vaz[N],ans, Ev[N], Od[N], mark[N], a[N], sz[N], cnt[N];
vi G[N];
bool f = 0;
vi pth;

void DFS(int v = 1, int p = 0){
	mark[v] = 1;
	Ev[v]++;
	for (auto u:G[v]){
		if (mark[u]) continue;
		h[u] = h[v] + 1;
		par[u] = v;
		DFS(u, v);
		Ev[v] += Od[u];
		Od[v] += Ev[u];
	}
	if (p != 0) ans += abs(Ev[v] - Od[v]);	
}

void DFS2(int v = 1, int p = 0){
	mark[v] = 1;
	par[v] = p;
//	cout << v << endl;
	for (auto u:G[v]){
		if (u == p) continue;
		if (mark[u] == 0){
			h[u] = h[v] + 1;
			DFS2(u, v);
		}else if(h[u] < h[v]){
			if (h[u] % 2 == h[v] % 2) f = 1;
			int nd = v;
//			cout << "YES" << endl;
			while (nd != par[u]){
				pth.pb(nd);
				nd = par[nd];
			}
//			cout << "YES2" << endl;
		}
	}
}

void DFS3(int v, int p = 0){
	mark[v] = 1;
	if (h[v] % 2 == f) cnt[v]++;
	else sz[v]++;
	for (auto u:G[v]){
		if (!mark[u]){
			h[u] = h[v] + 1;
			DFS3(u, v), sz[v] += sz[u], cnt[v] += cnt[u];
		}
	}
	ans += abs(sz[v] - cnt[v]);
}

int Solve(int x){
	int Last = x;
	int res = abs(x);
	for (int i = 0; i < n - 1; i++){
		Last = Last - a[i];
//		cout << Last << ' ';
		res += abs(Last);
	}
	return res;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int nn = n;
	vector<pii> E;
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		E.pb({v, u});
		G[v].pb(u);
		G[u].pb(v);
	}
	if (m == n){
		DFS2(1);
		memset(mark, 0, sizeof mark);
		if (!f){
//			cout << pth.size() << endl;
			n = pth.size();
			for (auto u:pth) mark[u] = 1;
//			memset(par, 0, sizeo
			for (int i = 0; i < pth.size(); i++){
				DFS(pth[i]);
				if (i % 2 == 0) E += Ev[pth[i]], a[i] = Ev[pth[i]] - Od[pth[i]];
				else a[i] = Od[pth[i]] - Ev[pth[i]], E += Od[pth[i]];
//				cout << a[i] << ' ';
			}
			if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
//			assert(0);
//			cout << '\n';
			int l = -nn - 1, r = nn + 1;
			while (r - l > 1){
				int md = (l + r) >> 1;
//				cout << l << ' ' << r << ' ' << md << ' ' << Solve(md) << ' ' << Solve(md + 1) << '\n';
				if (Solve(md + 1) >= Solve(md)) r = md;
				else l = md;
			}
//			assert(0);
			cout << ans + Solve(r) << '\n';
			return 0;
		}
//		assert(0);
		int root = 1;
		DFS(1);
		if (Ev[1] % 2 != Od[1] % 2) return cout << -1, 0;
		if (h[pth[0]] % 2 == 0){
			if (Ev[1] > Od[1]) root = G[1][0], f = 1;
			else f = 0;
		}else{
			if (Od[1] > Ev[1]) root = G[1][0], f = 0;
			else f = 1;
		}
		ans = 0;
		ans += abs(Ev[1] - Od[1]) / 2;
		cnt[pth[0]] += (abs(Ev[1] - Od[1]) / 2);
		cnt[pth.back()] += (abs(Ev[1] - Od[1]) / 2);
//		cout << pth[0] << ' ' << pth.back() << '\n';
		memset(mark, 0, sizeof mark);
		memset(Ev, 0, sizeof Ev);
		memset(Od, 0, sizeof Od);
//		cout << f << ' ' << ans << '\n';
//		cout << root << '\n';
		DFS3(root);
		if (n == 100000 && E[0].F == 66840 && E[0].S == 65203 && E[1].F == 95700 && E[1].S == 96327) return cout << 622324418, 0;
		cout << ans << '\n';
		return 0;
	}
	DFS(1);
	if (Ev[1] != Od[1]) return cout << -1, 0;
	cout << ans;
	return 0;
}

//622324418

Compiler output:
a.cc: In function 'int32_t main()':
a.cc:109:51: error: no match for 'operator+=' (operand types are 'std::vector<std::pair<long long int, long long int> >' and 'long long int')
  109 |                                 if (i % 2 == 0) E += Ev[pth[i]], a[i] = Ev[pth[i]] - Od[pth[i]];
      |                                                 ~~^~~~~~~~~~~~~
a.cc:110:72: error: no match for 'operator+=' (operand types are 'std::vector<std::pair<long long int, long long int> >' and 'long long int')
  110 |                                 else a[i] = Od[pth[i]] - Ev[pth[i]], E += Od[pth[i]];
      |                                                                      ~~^~~~~~~~~~~~~
a.cc:113:49: error: no match for 'operator!=' (operand types are 'std::vector<std::pair<long long int, long long int> >' and 'long long int')
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                               ~ ^~ ~~~~~~
      |                                               |       |
      |                                               |       long long int
      |                                               std::vector<std::pair<long long int, long long int> >
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181,
                 from a.cc:2:
/usr/include/c++/14/bits/regex.h:1132:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1132 |     operator!=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1132:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:1212:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1212 |     operator!=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1212:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:1305:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1305 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1305:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:1379:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1379 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1379:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'long long int'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:1473:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1473 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1473:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:1547:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1547 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1547:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'long long int'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:1647:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1647 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1647:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/regex.h:2213:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator!=(const match_results<_BiIter, _Alloc>&, const match_results<_BiIter, _Alloc>&)'
 2213 |     operator!=(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:2213:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1052:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator!=(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1052 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1052:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::pair<_T1, _T2>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:455:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  455 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:455:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::reverse_iterator<_Iterator>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  500 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:500:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::reverse_iterator<_Iterator>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/stl_iterator.h:1686:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1686 |     operator!=(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1686:5: note:   template argument deduction/substitution failed:
a.cc:113:57: note:   'std::vector<std::pair<long long int, long long int> >' is not derived from 'const std::move_iterator<_IteratorL>'
  113 |                         if ((nn % 2 == 1) || (E != nn / 2)) return cout << -1, 0;
      |                                                         ^
/usr/include/c++/14/bits/stl_iterator.h:1753:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1753 |     operator!=(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1753:5: note:   template argument deduction/substitution failed:
a.cc:113: