include iostream include vector include algorithm using namespace std

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
int n, m;
const int N = 1010;
int g[N][N];
int gu[N][N];
vector<int> order;
int cnt[N];
inline void dfs(int v) {
bool any = false;
for(int u = 0; u < n; u++) {
if(gu[v][u]) {
gu[v][u]--, gu[u][v]--;
dfs(u);
any = true;
}
}
if(any) order.pb(v);
}
vector<int> pr;
void goOrder() {
pr.assign(order.size(), 0);
for(int i = 1; i < order.size(); i++) {
pr[i] = pr[i-1];
int v = order[i-1], u = order[i];
if(g[v][u]) pr[i]++;
}
}
int calc(int i, int j) {
int res = 0;
for(;i < j; i++) {
int v = order[i], u = order[i+1];
if(g[v][u]) res++;
}
return min(res, j - i - res);
}
void solve() {
order.resize(0);
cin >>n >>m;
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) g[i][j] = false;
for(int i = 0; i < n; i++) cnt[i] = 0;
for(int i = 0; i < m; i++) {
int a, b;
cin >>a >>b;
g[a][b]++;
cnt[a]++, cnt[b]++;
gu[a][b]++, gu[b][a]++;
}
for(int i = 0; i < n; i++) {
if(cnt[i] & 1) {
cout <<-1 <<endl;
return;
}
}
int i = 0;
while(i < n && cnt[i] == 0) i++;
if(i == n) {
cout <<0 <<endl;
return;
}
dfs(i);
int os = order.size();
for(i = i + 1;i<n;i++) {
dfs(i);
if(order.size() != os) {
cout <<-1 <<endl;
return;
}
}
int ans = 0;
vector<int> last(n, -1);
while(!order.empty()) {
for(int i = 0; i < order.size(); i++) {
int v = order[i];
if(last[v] == -1) {
last[v] = i;
} else {
int lst = last[v];
ans += calc(lst, i);
order.erase(order.begin() + lst, order.begin() + i);
break;
}
}
}
cout <<ans <<endl;
}
int main() {
freopen("in.txt", "r", stdin);
int T;
cin >>T;
for(int t = 0; t < T; t++) {
solve();
}
return 0;
}