#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
int main() {
int n, cnt = 0;
vector <pair<string, string>> input;
map<string, int> mp;
vector<string> names;
vector <int> v;
string s1, s2;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s1 >> s2;
input.push_back({s1, s2});
}
if (n % 2) {
cout << -1;
return 0;
}
for (int i = 0; i < n; i++) {
mp[input[i].first] = cnt;
names.push_back(input[i].first);
cnt++;
}
v.resize(n);
for (int i = 0; i < n; i++) {
v[mp[input[i].first]] = mp[input[i].second];
}
int remaining = n;
// Check for pairs
for (int i = 0; i < n; i++) {
if (v[i] != -1 && i != v[i] && i == v[v[i]]) {
remaining -= 2;
cerr << "Paired: " << names[i] << " and " << names[v[i]] << endl;
v[v[i]] = -1; // Mark the pair as well
v[i] = -1; // Mark as paired
}
}
cerr << "Finished default pairing. Remaining: " << remaining << endl;
vector<int> indegree(n, 0); // Out-degree is 1 for all nodes
for(int i = 0; i < n; i++) {
if(v[i] != -1) {
indegree[v[i]]++;
}
}
set<int> candidates;
for (int i = 0; i < n; i++) {
if(v[i] != -1 && indegree[i] == 0) {
candidates.insert(i);
}
}
cerr << "Initial candidates with in-degree 0: " << candidates.size() << endl;
int moves = 0;
// Go through candidates (with in-degree 0)
while(!candidates.empty()) {
int current = *candidates.begin();
candidates.erase(candidates.begin());
if(v[current] != -1 && v[v[current]] != -1) {
cerr << "Pairing: " << names[current] << " and " << names[v[current]] << ". The edges are " << names[current] << " -> " << names[v[current]] << " -> " << names[v[v[current]]] << endl;
moves++;
remaining -= 2;
indegree[v[v[current]]]--;
if(indegree[v[v[current]]] == 0) {
candidates.insert(v[v[current]]);
}
int second = v[current];
v[current] = -1; // Mark as removed
v[second] = -1; // Mark the pair as removed
}
}
int self_loops = 0;
for(int i = 0; i < n; i++) {
if(v[i] == i) {
self_loops++;
v[i] = -1; // Mark self-loop as removed
remaining--;
}
}
// Count cycles and their sizes
int cycle_moves = 0;
for (int i = 0; i < n; i++) {
if(v[i] != -1 && v[i] != i) {
int cycle_size = 0;
int current = i;
int old;
cerr << "Starting cycle detection from: " << names[current] << endl;
while(v[current] != -1) {
old = current;
current = v[current];
cycle_size++;
v[old] = -1; // Mark as visited
}
if(cycle_size > 0) {
cycle_moves += (cycle_size + 1) / 2; // Each cycle of size k requires ceil(k/2) moves
cerr << "Cycle detected of size " << cycle_size << ". Moves needed: " << (cycle_size + 1) / 2 << endl;
}
remaining -= cycle_size;
}
}
cerr << "Finished processing candidates. Moves: " << moves << ", Remaining: " << remaining << ", Cycle moves: " << cycle_moves << ", Self-loops: " << self_loops << endl;
cout << moves + remaining + cycle_moves + self_loops;
return 0;
}
/*
4
a b
b c
c d
d a
*/
