#include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 1e5 + 5, inf = 1e9; vector<int> g[maxn], rev[maxn]; int vis[maxn], f[maxn]; void dfs(int u){ vis[u] = 1; 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; } } 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{ vector<int> deg(n + 1), c2(n + 1); for(int i = 1; i <= n; i++) if(g[i].size()) deg[g[i][0]]++; for(int i = 1; i <= n; i++){ if(g[i].empty()) continue; int v = g[i][0]; if(g[v].size() && g[v][0] == i && i != v) c2[i] = 1; } queue<int> q; for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i); int kept = 0; while(q.size()){ int u = q.front(); q.pop(); if(vis[u]) continue; int v = g[u][0]; if(!vis[v] && !c2[v] && u != v){ vis[u] = 1; vis[v] = 1; kept++; } deg[v]--; if(deg[v] == 0) q.push(v); } for(int i = 1; i <= n; i++){ if(vis[i]) continue; if(c2[i]){ int v = g[i][0]; if(!vis[v]){ vis[i] = vis[v] = 1; kept += 2; } }else{ int cur = i, len = 0; while(!vis[cur]){ vis[cur] = 1; len++; cur = g[cur][0]; } kept += len / 2; } } cout << n - kept; } }