#include<bits/stdc++.h> #define newl '\n' const int N = 1e5 + 10; const int V = 1e7 + 10; const long long INF = 1e18; const long long M = 1e9 + 7; struct Subtask{ int n,id; std::vector<int> par,f; std::map<std::string,int> m; int get(std::string str){ if(m.find(str) == m.end()){ m[str] = id++; } return m[str]; } Subtask() : id(0){ } void readData(){ std::cin >> n; par.assign(n + 1,0); f.assign(1 << n,V); for(int i = 1;i <= n;++i){ std::string su,sv; std::cin >> su >> sv; int u = get(su); int v = get(sv); par[u] = v; } } void solve(){ f[0] = 0; for(int mask = 0;mask < (1 << n);++mask){ std::vector<int> vec; for(int i = 0;i < n;++i){ if(!((mask >> i) & 1)){ vec.emplace_back(i); } } for(int i = 0;i < (int)vec.size();++i){ for(int j = i + 1;j < (int)vec.size();++j){ int u = vec[i]; int v = vec[j]; // std::cout << "IMP " << mask << " " << u << " " << v << newl; int nm = (mask | (1 << u) | (1 << v)); f[nm] = std::min(f[nm],f[mask] + (par[u] != v) + (par[v] != u)); } } } // assert(par[6] == 7); // assert(par[7] == 6); // std::cout << f[(1 << 6) | (1 << 7)] << newl; std::cout << (f[(1 << n) - 1] == V ? -1 : f[(1 << n) - 1]); } void main(){ readData(); solve(); } }; struct Solver{ int n,id,ans = 0; std::vector<bool> match; std::vector<std::vector<int>> adj,adj_rev; std::map<std::string,int> m; std::vector<int> par,vis,deg; int get(std::string str){ if(m[str] == 0){ m[str] = ++id; } return m[str]; } Solver() : id(0){ } void readData(){ std::cin >> n; match.assign(n + 1,0); adj.resize(n + 1); adj_rev.resize(n + 1); par.assign(n + 1,0); vis.assign(n + 1,0); deg.assign(n + 1,0); for(int i = 1;i <= n;++i){ std::string su,sv; std::cin >> su >> sv; int u = get(su); int v = get(sv); par[u] = v; adj[par[u]].emplace_back(u); adj_rev[u].emplace_back(par[u]); ++deg[par[u]]; // std::cout << u << " " << v << newl; } } void prepare(){ std::queue<int> q; for(int i = 1;i <= n;++i){ if(deg[i] == 0){ q.push(i); } } while(!q.empty()){ int u = q.front(); q.pop(); for(int v : adj_rev[u]){ --deg[v]; if(deg[v] == 0){ q.push(v); } } } } void dfs(int u){ // if(u == 3){ // std::cerr // } vis[u] = true; for(int v : adj[u]){ if(vis[v] || v == u){ continue; } dfs(v); if(!match[v] && !match[u]){ match[u] = match[v] = true; ++ans; } } } void dfs1(int u){ // assert(deg[u] > 0); vis[u] = true; for(int v : adj[u]){ if(vis[v] || v == u || deg[v] > 0){ continue; } // assert(deg[v] == 0); dfs1(v); if(!match[v] && !match[u]){ match[u] = match[v] = true; ++ans; } } } void dfs_cycle(int u){ // std::cerr << "IMP " << u << newl; vis[u] = true; for(int v : adj[u]){ if(deg[v] == 0){ continue; } if(!vis[v]){ dfs_cycle(v); } if(!match[v] && !match[u]){ match[u] = match[v] = true; ++ans; } } } void solve(){ // for(int i = 1;i <= n;++i){ // std::cout << deg[i] << " "; // } // std::cout << newl; // assert(par[3] != 1); // for(int v : adj[1]){ // std::cout << "NEXT 1 " << v << newl; // } if(n & 1){ std::cout << -1; return; } for(int i = 1;i <= n;++i){ if(par[par[i]] == i){ if(par[i] > i){ match[i] = match[par[i]] = true; } dfs(i); dfs(par[i]); }else{ if(par[i] != i && deg[i] > 0){ // assert(false); dfs1(i); } } } // for(int i = 1;i <= n;++i){ // std::cout << match[i] << " "; // } // std::cout << newl; // std::cout << "IMP " << ans << newl; // assert(match[par[3]] == true && !vis[3]); for(int i = 1;i <= n;++i){ if(par[i] == i){ dfs(i); } } std::fill(vis.begin() + 1,vis.end(),0); for(int i = 1;i <= n;++i){ if(deg[i] > 0 && !vis[i]){ dfs_cycle(i); } } for(int i = 1;i <= n;++i){ // std::cout << match[i] << " "; ans += !match[i]; } std::cout << ans; } void main(){ readData(); prepare(); solve(); } }; int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);std::cout.tie(nullptr); // freopen("A.inp","r",stdin); // freopen("A.out","w",stdout); Solver().main(); return 0; }