#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<bool> match; // std::vector<std::vector<int>> adj; // std::map<std::string,int> m; // std::vector<int> par,vis; // int get(std::string str){ // if(m[str] == 0){ // m[str] = ++id; // } // return m[str]; // } // Subtask() : id(0){ // // } // void readData(){ // std::cin >> n; // adj.resize(n + 1); // par.assign(n + 1,0); // vis.assign(n + 1,0); // match.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); //// std::cout << u << " " << v << newl; // } // } // 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; // } // } // } // void solve(){ // if(n & 1){ // std::cout << -1; // return; // } // for(int i = 1;i <= n;++i){ // if(i == par[i]){ // dfs(i); // } // } // int ans = 0; // for(int i = 1;i <= n;++i){ // ans += match[i]; //// std::cout << match[i] << " "; // } // ans /= 2; // for(int i = 1;i <= n;++i){ // ans += !match[i]; //// std::cout << match[i] << " "; // } //// for(int i = 1;i <= n;++i){ //// ans -= (par[par[i]] == i && i < par[i]); //// } // std::cout << ans; // } // 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]]; 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[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); Solver().main(); return 0; }