#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 3; const int inf32 = 1e9; int n, to[N], in_deg[N]; namespace sub1 { int dp[1 << 20]; void solve(){ fill(dp + 1, dp + (1 << n), inf32); vector<int> gr; for (int mask = 1; mask < (1 << n); ++mask) if (__builtin_popcount(mask) % 2 == 0){ gr.clear(); for (int i = 0; i < n; ++i) if (mask >> i & 1) gr.push_back(i); for (int i = 0; i < (int)gr.size(); ++i){ for (int j = i + 1; j < (int)gr.size(); ++j){ int u = gr[i], v = gr[j]; if (dp[mask ^ (1 << u) ^ (1 << v)] != inf32){ int c; if (to[u] == v && to[v] == u) c = 0; else if (to[u] == v || to[v] == u) c = 1; else c = 2; dp[mask] = min(dp[mask], dp[mask ^ (1 << u) ^ (1 << v)] + c); } } } } cout << dp[(1 << n) - 1] << '\n'; } }; namespace sub2 { bool check(){ for (int i = 0; i < n; ++i){ if (in_deg[i] == 0) return false; } return true; } vector<bool> vis(N); void solve(){ int res = 0; for (int i = 0; i < n; ++i) if (!vis[i]){ int sz = 1; vis[i] = true; for (int u = to[i]; u != i; u = to[u]){ ++sz; vis[u] = true; } if (sz > 2) res += sz / 2; if (sz & 1) ++res; } cout << res << '\n'; } }; namespace sub3 { vector<int> g[N]; int dp[N][2]; bool check(){ return true; } void dfs(int u, int pre){ bool haschild = false; for (int v : g[u]) if (v != pre){ dfs(v, u); if (!haschild){ haschild = true; dp[u][1] = 1; } dp[u][1] += dp[v][0]; dp[u][0] += max(dp[v][0], dp[v][1]); } } void solve(){ for (int i = 0; i < n; ++i) if (to[i] != i) g[to[i]].push_back(i); int matched = 0; for (int i = 0; i < n; ++i) if (to[i] == i){ dfs(i, -1); matched += max(dp[i][0], dp[i][1]); } cout << matched + (n - 2 * matched) << '\n'; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; if (n & 1){ cout << "-1\n"; return 0; } vector<pair<string, string>> R; vector<string> people; for (int i = 0; i < n; ++i){ string a, b; cin >> a >> b; R.emplace_back(a, b); people.push_back(a), people.push_back(b); } sort(begin(people), end(people)); people.erase(unique(begin(people), end(people)), end(people)); for (auto [a, b] : R){ int i = lower_bound(begin(people), end(people), a) - begin(people); int j = lower_bound(begin(people), end(people), b) - begin(people); to[i] = j; ++in_deg[j]; } if (n <= 20){ sub1::solve(); return 0; } if (sub2::check()){ sub2::solve(); return 0; } if (sub3::check()){ sub3::solve(); return 0; } }