#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define all(x) x.begin(), x.end() #define SZ(x) int(x.size()) const int MXN = 1e5+5; int n, p[MXN], ans; vector<string> names; pair<string, string> edges[MXN]; int GI(string s) { return lower_bound(all(names), s)-names.begin(); } int vis[MXN]; bool cyc[MXN]; void dfs(int v) { vis[v] = 1; if(vis[p[v]]==1) { for(int u=p[v]; u!=v; u=p[u]) cyc[u] = 1; cyc[v] = 1; vis[v] = 2; return; } else if(vis[p[v]]==2){ vis[v] = 2; return; } dfs(p[v]); vis[v] = 2; } vector<int> g[MXN]; int dp[MXN][2]; void dfs2(int v) { for(int u : g[v]) { dfs2(u); dp[v][1] = max(dp[v][1]+dp[u][1], dp[v][0]+dp[u][0]+1); dp[v][0] += dp[u][1]; } } vector<int> vec; void dfs3(int v) { vis[v] = 3; vec.push_back(v); if(vis[p[v]]!=3) dfs3(p[v]); } bool mark[MXN]; int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n; for(int i=0; i<n; i++) { cin >> edges[i].X >> edges[i].Y; names.push_back(edges[i].X); names.push_back(edges[i].Y); } if(n&1) { cout << "-1\n"; return 0; } sort(all(names)); names.resize(unique(all(names))-names.begin()); for(int i=0; i<n; i++) p[GI(edges[i].X)] = GI(edges[i].Y); for(int i=0; i<n; i++) if(p[i]!=i && p[p[i]]==i) mark[p[i]] = mark[i] = 1, p[p[i]] = p[i], p[i] = i, ans += 2; for(int i=0; i<n; i++) if(mark[p[i]]) p[i] = i; for(int i=0; i<n; i++) if(!vis[i]) dfs(i); for(int i=0; i<n; i++) if(!cyc[i]) g[p[i]].push_back(i); for(int i=0; i<n; i++) if(cyc[i]) { dfs2(i); ans += dp[i][1]; } for(int i=0; i<n; i++) if(cyc[i] && vis[i]!=3) { dfs3(i); bool fnd = 0; for(int j=0; j<SZ(vec); j++) if(dp[vec[j]][0]<dp[vec[j]][1]) { int ln = 0; for(int k=(j+1)%SZ(vec); k!=j; (++k)%=SZ(vec)) { if(dp[vec[k]][0]<dp[vec[k]][1]) { ans += ln/2; ln = 0; } else ln++; } ans += ln/2; fnd = 1; break; } if(!fnd) ans += SZ(vec)/2; vec.clear(); } cout << n-ans << '\n'; return 0; }