#ifndef hari64 #include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define debug(...) #else #include "util/viewer.hpp" #define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__) #endif // clang-format off using namespace std; using ll = long long; using ld = long double; using pii = pair; using pll = pair; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; using vi = vc; using vll = vc; using vpii = vc; using vpll = vc; using vvi = vc; using vvll = vc; using vvpi = vc; using vvpll = vc; constexpr int INF = 1001001001; constexpr long long INFll = 1001001001001001001; template bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; } // clang-format on int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector> UVs(M); vi deg(2 * N, 0); for (int i = 0; i < M; i++) { int U; int V; cin >> U >> V; U--; V--; UVs[i] = {U, V}; deg[U]++; deg[N + V]++; } int oddCnt = 0; for (int i = 0; i < N; i++) { oddCnt += abs(deg[i] - deg[N + i]); } debug(oddCnt); if (oddCnt == 0) { cout << 0 << endl; } else { if (oddCnt % 2 == 1) { cout << -1 << endl; } else { cout << oddCnt / 2 - 1 << endl; } } return 0; }