#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; 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); 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); ++deg[par[u]]; } } 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[u]){ --deg[v]; if(deg[v] == 0){ q.push(v); } } } } void dfs(int u){ 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){ vis[u] = true; for(int v : adj[u]){ if(vis[v] || v == u || deg[v] > 0){ continue; } dfs(v); if(!match[v] && !match[u]){ match[u] = match[v] = true; ++ans; } } } void dfs_cycle(int u){ vis[u] = true; for(int v : adj[u]){ if(vis[v] || v == u || deg[v] == 0){ continue; } dfs(v); if(!match[v] && !match[u]){ match[u] = match[v] = true; ++ans; } } } void solve(){ for(int i = 1;i <= n;++i){ if(par[i] == i){ dfs(i); }else{ // if(par[par[i]] == i){ // if(par[i] > i){ // match[i] = match[par[i]] = true; // } // dfs(i); // dfs(par[i]); // }else{ // dfs1(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); Subtask().main(); return 0; }