# 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 #include #include 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 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 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 < 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 <>T; for(int t = 0; t < T; t++) { solve(); } return 0; } ```