#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
int n; cin >> n;
map<string, int> mp;
vector<int> a(n);
vector<vector<int>> adj2(n);
vector<int> indeg(n);
for (int i = 0; i < n; i++) {
string s, t;
cin >> s >> t;
if (!mp.count(s)) mp[s] = mp.size();
if (!mp.count(t)) mp[t] = mp.size();
a[mp[s]] = mp[t];
adj2[mp[s]].push_back(mp[t]);
adj2[mp[t]].push_back(mp[s]);
indeg[mp[t]]++;
}
if (n & 1) {
cout << -1 << '\n'; return;
}
vector<bool> vis(n), dir(n), vis3(n), in_ccl(n);
int ans = 0, extra = 0;
for (int i = 0; i < n; i++) if (!vis[i]) {
vector<int> got;
queue<int> q;
auto dfs = [&](auto&& s, int v) -> void {
got.emplace_back(v);
vis[v] = 1;
if (!indeg[v]) q.push(v);
for (int u : adj2[v]) if (!vis[u]) s(s, u);
};
dfs(dfs, i);
while (q.size()) {
int v = q.front(); q.pop();
if (dir[v]) continue;
int nxt = a[v];
if (!dir[nxt]) {
dir[nxt] = dir[v] = 1;
ans++;
}
else {
dir[v] = 1;
extra++;
// we need to find someone else
}
if (--indeg[nxt] == 0) q.push(nxt);
}
int to = i;
while (!vis3[to]) vis3[to] = 1, to = a[to];
while (!in_ccl[to]) in_ccl[to] = 1, to = a[to];
int starting = -1, sx = -1;
for (int v : got) if (in_ccl[v]) {
sx = v;
if (dir[v] && !dir[a[v]]) {
starting = v; break;
}
}
// if we dont have, then arbitrary is fine
assert(~sx);
if (!~starting) starting = sx;
int v = starting;
for (int i = 0; i < sz(got); i++, v = a[v]) if (!dir[v]) {
int nxt = a[v];
if (v == nxt) {
dir[v] = 1;
extra++; continue;
}
if (!dir[nxt]) {
dir[nxt] = dir[v] = 1;
ans += a[nxt] != v;
}
else {
dir[v] = 1;
extra++;
}
}
}
cout << ans + extra << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while (t--) test_case();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
273 ms |
17236 KB |
Output is correct |
| 5 |
Correct |
266 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
293 ms |
17656 KB |
Output is correct |
| 7 |
Correct |
234 ms |
14428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
266 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
