#include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 1e5 + 5, inf = 1e9; vector<int> g[100005], rev[100005]; int vis[maxn], f[maxn], ans, sz; void dfs(int u){ vis[u] = 1; sz++; for(int v: g[u]){ if(!vis[v]) dfs(v); } } void dfs2(int u){ vis[u] = 1; for(int v: rev[u]){ if(vis[v] || v == u) continue; dfs2(v); if(!f[v] && !f[u]) f[u] = f[v] = 1, ans++; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<vector<int>> has; if(n <= 20){ has = vector<vector<int>>(22, vector<int>(22)); } int id = 1; map<string, int> mp; vector<int> ok(n + 1), skibidivertice; for(int i = 1; i <= n; i++){ string s, t; cin >> s >> t; if(!mp.count(s)) mp[s] = id++; if(!mp.count(t)) mp[t] = id++; int u = mp[s], v = mp[t]; g[u].push_back(v); ok[v] = 1; if(n <= 20) has[u - 1][v - 1] = 1; if(u == v) skibidivertice.push_back(u); } bool sub2 = true; for(int i = 1; i <= n; i++) sub2 &= (ok[i]); if(n & 1){ cout << -1; return 0; } if(n <= 20){ vector<int> dp(1 << n, inf); dp[0] = 0; for(int mask = 0; mask < (1 << n); mask++){ if(__builtin_popcount(mask) % 2) continue; for(int i = 0; i < n; i++){ if(((mask >> i) & 1) == 1 || dp[mask]== inf) continue; for(int j = 0; j < n; j++){ if(((mask >> j) & 1) == 0){ int nm = mask ^ (1 << i) ^ (1 << j); dp[nm] = min(dp[nm], dp[mask] + (has[i][j] == 0) + (has[j][i] == 0)); } } } } cout << dp[(1 << n) - 1]; }else if(sub2){ int res = 0; for(int i = 1; i <= n; i++){ if(!vis[i]){ sz = 0; dfs(i); if(sz != 2) res += (sz + 1) / 2; } } cout << res; }else{ for(int i = 1; i <= n; i++){ for(int x: g[i]) rev[x].push_back(i); } for(int x: skibidivertice) dfs2(x); for(int i = 1; i <= n; i++) ans += !f[i]; cout << ans; } }