#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
constexpr int inf = 1e9 + 7;
vector<int> par, dp1, dp2, lft; // 1 - points up, 2 - points down
vector<vector<int>> son;
vector<int> roots;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, tmp = 0;
map<string, int> mp;
cin >> n;
if(n % 2 == 1) { cout << -1; return 0; }
par.resize(n + 1);
son.resize(n + 1);
dp1.resize(n + 1, inf);
dp2.resize(n + 1, inf);
lft.resize(n + 1);
string s1, s2;
rep(i, 0, n) {
cin >> s1 >> s2;
if(!mp[s1]) mp[s1] = ++tmp;
if(!mp[s2]) mp[s2] = ++tmp;
par[mp[s1]] = mp[s2];
son[mp[s2]].pb(mp[s1]);
}
rep(i, 1, n + 1) {
if(son[i].empty() || (son[i].size() == 1 && par[i] == i)) dp1[i] = 0, dp2[i] = 1, lft[par[i]]--, lft[i] = 2;
else lft[i] += (int)son[i].size() - (par[i] == i);
if(par[i] == i) roots.pb(i);
}
queue<int> q;
rep(i, 1, n + 1) if(lft[i] == 0) q.push(i);
while(!q.empty()) {
auto v = q.front();
q.pop();
dp1[v] = 0;
repIn(u, son[v]) if(u != v) dp1[v] += dp2[u];
dp2[v] = dp1[v] + 1;
repIn(u, son[v]) if(u != v) dp2[v] = min(dp2[v], dp1[v] - dp2[u] + dp1[u] + 1);
// TODO subsize and ifs for free ones
if(par[v] != v) lft[par[v]]--;
if(par[v] != v && !lft[par[v]]) q.push(par[v]);
}
DEBUG {
repIn2(k, v, mp) DC << k << ' ' << dp1[v] << ' ' << dp2[v] << eol;
}
int ans = 0;
repIn(i, roots) ans += dp2[i];
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |