#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define pli pair<ll, int> #define debug(x) cout << #x << " = " << x << '\n' #define all(a) a.begin(), a.end() #define SZ(a) (int)(a).size() const int N = 1e6 + 5; const int mod = 1e9 + 7; const ll inf64 = 3e18; const int inf32 = 2e9 + 5; int n, g[N]; namespace sub1 { int dp[1 << 20][25]; void sol() { memset(dp, 63, sizeof dp); dp[0][0] = 0; for(int msk = 1; msk < (1 << n); msk++) { int popcnt = __builtin_popcount(msk); if(popcnt == 1) { int p = -1; for(int i = 0; i < n; i++) if(msk >> i & 1) { p = i; break; } dp[msk][p] = 0; continue; } if(popcnt & 1) { for(int i = 0; i < n; i++) if(msk >> i & 1) dp[msk][i] = min(dp[msk][i], dp[msk ^ (1 << i)][0]); } else { for(int i = 0; i < n; i++) if(msk >> i & 1) { for(int j = 0; j < n; j++) if(i != j && (msk >> j & 1)) dp[msk][0] = min(dp[msk][0], dp[msk ^ (1 << i)][j] + (g[i + 1] != j + 1) + (g[j + 1] != i + 1)); } } } cout << dp[(1 << n) - 1][0]; } }; namespace sub2 { bool check() { vector<bool> chk(n + 3, 0); for(int i = 1; i <= n; i++) chk[g[i]] = true; for(int i = 1; i <= n; i++) if(!chk[i]) return false; return true; } bool vis[N]; int cnt; void dfs(int u) { cnt++, vis[u] = true; if(!vis[g[u]]) dfs(g[u]); } void sol() { int ans = 0; for(int i = 1; i <= n; i++) if(!vis[i]) { cnt = 0; dfs(i); if(cnt != 2) ans += (cnt + 1) / 2; } cout << ans << '\n'; } } namespace sub3 { int par[N], dp[N][2], cnt; vector<int> child[N]; void dfs(int u) { cnt++; for(int v : child[u]) { dfs(v); dp[u][0] += max(dp[v][0], dp[v][1]); } for(int v : child[u]) dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[v][0], dp[v][1]) + dp[v][0] + 1); // debug(u); // debug(dp[u][0]); // debug(dp[u][1]); } void sol() { for(int i = 1; i <= n; i++) { par[i] = g[i]; if(par[i] != i) child[par[i]].push_back(i); } int ans = 0; for(int i = 1; i <= n; i++) if(par[i] == i) { cnt = 0; dfs(i); int mx = max(dp[i][0], dp[i][1]); ans += mx + (cnt - 2 * mx); } cout << ans << '\n'; } } void solve() { int q; cin >> q; map<string, int> mp; for(int i = 1; i <= q; i++) { string s, t; cin >> s >> t; if(!mp.count(s)) mp[s] = ++n; if(!mp.count(t)) mp[t] = ++n; g[mp[s]] = mp[t]; } if(n & 1) { cout << -1; return; } if(n <= 20) return sub1::sol(); if(sub2::check()) return sub2::sol(); return sub3::sol(); } int main() { auto start = chrono::steady_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } int test = 1; // cin >> test; while(test--) solve(); chrono::duration<double> elapsed {chrono::steady_clock::now() - start}; cerr << "\n>> Runtime: " << elapsed.count() << "s\n"; }

polygon.cpp: In function 'int main()':
polygon.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~