#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
// Hàm tính chi phí cho một chu trình hoặc một chuỗi các node "mồ côi"
void process_remaining_structure(int start_node, int& cost, std::vector<bool>& paired, const std::vector<int>& loves) {
// Bỏ qua nếu node này đã được xử lý
if (paired[start_node]) {
return;
}
// Đo độ dài của chu trình hoặc đường đi của các node chưa được ghép cặp
int k = 0;
int current_node = start_node;
while (!paired[current_node]) {
paired[current_node] = true;
current_node = loves[current_node];
k++;
}
// Thêm chi phí dựa trên độ dài k
// Nếu k=1, đó là một node mồ côi hoặc một vòng lặp tự thân -> chi phí là 1
if (k == 1) {
cost += 1;
}
// Nếu k > 2, đó là một "đa giác tình yêu"
else if (k > 2) {
cost += (k / 2) + (k % 2);
}
// Nếu k=2, đó là một mối quan hệ, nhưng nó đã phải được xử lý ở Giai đoạn 0.
// Nếu nó đến được đây, có nghĩa là nó không phải là một mối quan hệ 0 chi phí ban đầu.
// Tuy nhiên, logic của Giai đoạn 0 đảm bảo các cặp 0 chi phí không lọt vào đây.
// Bất kỳ cặp k=2 nào được tìm thấy ở đây đều là một phần của chuỗi phức tạp hơn đã được đơn giản hóa.
// Chi phí của nó vẫn là 0.
}
int main() {
// Tăng tốc độ I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
// Nếu N lẻ, không thể ghép cặp tất cả mọi người
if (n % 2 != 0) {
std::cout << -1 << std::endl;
return 0;
}
std::map<std::string, int> name_to_id;
int next_id = 0;
// Hàm lambda để lấy hoặc tạo ID cho tên
auto get_id = [&](const std::string& name) {
if (name_to_id.find(name) == name_to_id.end()) {
name_to_id[name] = next_id++;
}
return name_to_id[name];
};
std::vector<int> loves(n);
std::vector<int> in_degree(n, 0);
// Đọc input và xây dựng đồ thị
for (int i = 0; i < n; ++i) {
std::string s, t;
std::cin >> s >> t;
int id_s = get_id(s);
int id_t = get_id(t);
loves[id_s] = id_t;
in_degree[id_t]++;
}
int cost = 0;
std::vector<bool> paired(n, false);
// *** GIAI ĐOẠN 0: Ưu tiên xử lý các cặp có sẵn (chi phí 0) ***
for (int i = 0; i < n; ++i) {
if (paired[i]) continue;
int j = loves[i];
// Kiểm tra xem j có yêu ngược lại i không, và j phải khác i
if (i != j && loves[j] == i) {
paired[i] = true;
paired[j] = true;
}
}
// *** GIAI ĐOẠN 1: Xử lý các đường đi từ node lá ***
std::queue<int> q;
for (int i = 0; i < n; ++i) {
// Chỉ thêm các node lá CHƯA được ghép cặp
if (!paired[i] && in_degree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
// Node u có thể đã được ghép cặp trong một lần lặp trước đó
if (paired[u]) {
continue;
}
int v = loves[u];
// Nếu mục tiêu v đã được ghép cặp (ví dụ ở Giai đoạn 0),
// thì u trở thành mồ côi và sẽ được xử lý ở Giai đoạn 2.
if (paired[v]) {
continue;
}
// Ghép cặp u với v. Chi phí là 1 (cho v).
cost += 1;
paired[u] = true;
paired[v] = true;
// Cập nhật in-degree cho node mà v yêu
int w = loves[v];
in_degree[w]--;
// Nếu w trở thành node lá và chưa được ghép cặp, thêm vào hàng đợi
if (in_degree[w] == 0 && !paired[w]) {
q.push(w);
}
}
// *** GIAI ĐOẠN 2: Xử lý các chu trình và các node mồ côi còn lại ***
for (int i = 0; i < n; ++i) {
if (!paired[i]) {
process_remaining_structure(i, cost, paired, loves);
}
}
std::cout << cost << std::endl;
return 0;
}
