#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]; } }; 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(); } 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:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~