#include<unordered_map> #include<unordered_set> #include<algorithm> #include<iostream> #include<cstdlib> #include<iomanip> #include<cstring> #include<cassert> #include<numeric> #include<vector> #include<string> #include<chrono> #include<random> #include<stack> #include<queue> #include<cmath> #include<set> #include<map> #include<ios> using namespace std; signed main() { int x = 0, n; cin >> n; vector<unordered_set<int>>gp(n); unordered_map<string, int>mp; for (int i = 0; i < n; i++) { string a, b; cin >> a >> b; if (mp.find(a) == mp.end()) mp[a] = x++; if (mp.find(b) == mp.end()) mp[b] = x++; int u = mp[a], v = mp[b]; gp[u].insert(v); } if (n % 2) { cout << -1; return 0; } if (n <= 20) { vector<pair<int, int>>dp((1 << n), { 1e9,1e9 }); dp[0] = { 0,0 }; for (int i = 0; i < (1 << n); i++) { int cnt = 0; for (int j = 0; j < n; j++) if ((1 << j) & i) cnt++; if (cnt % 2 == 0) { for (int j = 0; j < n; j++) { if ((1 << j) & i) continue; if (dp[i + (1 << j)].first > dp[i].first) { dp[i + (1 << j)].first = dp[i].first; dp[i + (1 << j)].second = j; } } } else { int x = dp[i].second; for (int j = 0; j < n; j++) { if ((1 << j) & i) continue; int cnt = 0; if (gp[x].find(j) == gp[x].end()) cnt++; if (gp[j].find(x) == gp[j].end()) cnt++; dp[i + (1 << j)].first = min(dp[i + (1 << j)].first, dp[i].first + cnt); } } } cout << dp[(1 << n) - 1].first; return 0; } bool fl = 0; int cnt = 0, ax = 0, ans = 0, ans1 = 0; queue<int>q; vector<int>vis(n); //cout << "----\n"; for (int i = 0; i < n; i++) { if (vis[i]) continue; cnt = 0; bool fl1 = 0; vis[i] = i + 1; q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (auto& v : gp[u]) { if (vis[v]) { //cout << u << " " << v << endl; if (vis[u] == vis[v] && u != v) fl1 = 1; continue; } q.push(v); vis[v] = i + 1; } } fl |= fl1; if (cnt != 2) { if (cnt % 2)ax++; ans += cnt / 2; } } //cout << "----\n"; //cout << endl << "fl = " << fl << endl; if (!fl) { //cout << "brat\n"; cnt = 0, ans = 0; vector<int>indeg(n),par(n); stack<int>st; vis = vector<int>(n); for (int i = 0; i < n; i++) { for (auto& j : gp[i]) indeg[j]++, par[i] = j; } for (int i = 0; i < n; i++) if (indeg[i] == 0) { st.push(i); } for (int i = 0; i < n; i++) if (par[i] == i) indeg[i]--; while (!st.empty()) { int u = st.top(); st.pop(); int v = par[u]; if (indeg[v] == 1) { vis[u] = vis[v] = true; indeg[v]--; ans++; int x = par[v]; if (x != v) indeg[x]--; if (indeg[x] == 0) st.push(x); } } for (int i = 0; i < n; i++) if (par[i] == i) indeg[i]++; for (int i = 0; i < n; i++) if (indeg[i] == 0 && !vis[i]) { st.push(i); } for (int i = 0; i < n; i++) if (par[i] == i) indeg[i]--; while (!st.empty()) { int u = st.top(); st.pop(); int v = par[u]; indeg[v]--; if (indeg[v] == 0) { vis[v] = vis[u] = true; int x = par[v]; ans++; if (x != v) indeg[x]--; if (x != v && indeg[x] == 0) st.push(x); } else { cnt++; vis[u] = true; } } for (int i = 0; i < n; i++) ans += vis[i] == 0; cout << ans + cnt << endl; } else cout << ans + ax << endl; }