#include <bits/stdc++.h> using namespace std; int n; int nxt[100000], f[2][100000], h[2][2][100000]; bool check[100000]; string p[100000]; map<string, int> mp; vector<int> g[100000], temp; vector<vector<int>> v; inline void Subtask1() { vector<int> g; g.resize(1 << n, 1e9); g[0] = 0; for (int i = 0; i < (1 << n); ++i) { if (__builtin_popcount(i) & 1) { continue; } for (int j = 0; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (((i >> j) & 1) && ((i >> k) & 1)) { g[i] = min(g[i], (nxt[j] != k) + (nxt[k] != j) + g[i - (1 << j) - (1 << k)]); } } } } cout << g[(1 << n) - 1]; } inline void DFS(int node) { vector<int> cur; check[node] = true; temp.push_back(node); if (check[nxt[node]]) { while (!temp.empty()) { cur.push_back(temp.back()); if (temp.back() == nxt[node]) { break; } temp.pop_back(); } if (cur.back() == nxt[node]) { reverse(cur.begin(), cur.end()); v.push_back(cur); } } else { DFS(nxt[node]); } } inline void DFS1(int node) { f[0][node] = 1; f[1][node] = 1e9; for (auto &i : g[node]) { if (!check[i]) { DFS1(i); f[1][node] = min(f[1][node] + min(f[1][i], f[0][i]), f[0][node] + f[0][i] - 1); f[0][node] += min(f[0][i], f[1][i]); } } } inline void Subtask4() { int res = 0; for (int i = 0; i < n; ++i) { if (!check[i]) { temp.clear(); DFS(i); } } fill_n(check, n, 0); for (auto &i : v) { for (auto &j : i) { check[j] = true; } } for (auto &i : v) { for (auto &j : i) { DFS1(j); } if (i.size() == 1) { res += min(f[1][i.back()], f[0][i.back()]); continue; } for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { fill_n(h[j][k], i.size(), 1e9); } } // h[i][j][k] : i for the first one take / pass, j for the k'th one take / pass, k is the index h[0][0][1] = f[0][i[0]] + f[0][i[1]]; h[0][1][1] = f[0][i[0]] + f[1][i[1]]; h[1][0][1] = f[1][i[0]] + f[0][i[1]]; h[1][1][1] = min(f[1][i[0]] + f[1][i[1]], f[0][i[0]] + f[0][i[1]] - 1); for (int j = 2; j < i.size(); ++j) { h[0][0][j] = f[0][i[j]] + min(h[0][0][j - 1], h[0][1][j - 1]); h[0][1][j] = min(f[1][i[j]] + min(h[0][0][j - 1], h[0][1][j - 1]), // count independently f[0][i[j]] + h[0][0][j - 1] - 1); // connect with the previous one h[1][0][j] = f[0][i[j]] + min(h[1][0][j - 1], h[1][1][j - 1]); h[1][1][j] = min(f[1][i[j]] + min(h[1][0][j - 1], h[1][1][j - 1]), f[0][i[j]] + h[1][0][j - 1] - 1); } res += min({h[0][0][i.size() - 1] - 1, h[0][1][i.size() - 1], h[1][0][i.size() - 1], h[1][1][i.size() - 1]}); } cout << res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; ++i) { cin >> p[i]; mp[p[i]] = i; cin >> p[i]; } for (int i = 0; i < n; ++i) { nxt[i] = mp[p[i]]; g[mp[p[i]]].push_back(i); } if (n & 1) { cout << -1; return 0; } if (n <= 20) { Subtask1(); return 0; } Subtask4(); return 0; }