#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b or a == -1) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
void prepare(); void main_code();
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const bool MULTITEST = 0; prepare();
int num_test = 1; if (MULTITEST) cin >> num_test;
while (num_test--) { main_code(); }
}
void prepare() {};
stack<int> st;
bool vis[N];
vector<int> cyc, g[N];
void dfs(int u, int p) {
st.push(u);
vis[u] = 1;
for(int v : g[u]) if (v ^ p) {
if (vis[v] == 0) {
dfs(v, u);
} else {
// (u->v) canh nguoc
while (sz(st)){
int u = st.top();
st.pop();
cyc.push_back(u);
if (u == v) break ;
}
return ;
}
}
if (sz(st))
st.pop();
}
bool on[N];
int dp[N][2][2], s[2][2];
const int INF = (int)1e8;
void dfs2(int u, int p) {
vector<int> child;
for(int v : g[u]) if (v != p and !on[v]) {
dfs2(v, u);
child.push_back(v);
}
if (sz(child) == 0) {
dp[u][0][0] = 0;
dp[u][0][1] = 1;
return ;
}
// dp(i, j : dinh i da thoa man chua, k : dinh i co phai la blue khong)
FOR(i, 0, 1) FOR(j, 0, 1) s[i][j] = 0;
for(int v : child) {
FOR(i, 0, 1) FOR(j, 0, 1)
s[i][j] += dp[v][i][j];
}
dp[u][0][0] = s[1][0];
for(int v : child) {
dp[u][1][0] = min(dp[u][1][0], dp[v][1][1] + s[1][0] - dp[v][1][0]);
}
dp[u][0][1] = s[0][0] + 1;
for(int v : child) {
dp[u][1][1] = min(dp[u][1][1], dp[v][0][1] + s[0][0] - dp[v][0][0] + 1);
}
// cout << "u: " << u << nl;
// FOR(i, 0, 1) FOR(j, 0, 1)
// cout << i << ' ' << j << ' ' << dp[u][i][j] << nl;
}
bool saf(int a, int b, int c, int d) {
if ( (a & c) or (b & d) ) return 0;
return 1;
}
long long f[N][2][2];
void main_code() {
int n; cin >> n;
for(int i = 1; i <= n; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
FOR(i, 1, n) FOR(j, 0, 1) FOR(k, 0, 1)
dp[i][j][k] = INF;
dfs(1, 0);
for(int x : cyc) on[x] = 1;
for(int x : cyc) {
dfs2(x, 0);
// cout << x << ' ';
}
// cout << nl;
long long ans = INT_MAX;
memset(f, -1, sizeof f);
int m = sz(cyc);
FOR(ia, 0, 1) FOR(ja, 0, 1)
FOR(ib, 0, 1) FOR(jb, 0, 1) if (saf(ia, ja, ib, jb)
and dp[cyc[0]][ia][ja] < INF and dp[cyc.back()][ib][jb] < INF) {
// (ia, ja) state ta chon cho 1
// (ib, jb) state ta chon cho m - 1
f[0][ia][ja] = dp[cyc[0]][ia][ja];
// cout << "state: ";
// cout << ia << ' ' << ja << ' ' << ib << ' ' << jb << nl;
FOR(t, 0, m - 2)
FOR(i, 0, 1) FOR(j, 0, 1) if (f[t][i][j] != -1) {
// cout << t << ' ' << i << ' ' << j << ' ' << f[t][i][j] << nl;
if (t == 0) {
FOR(u, 0, 1) FOR(v, 0, 1) {
if ( (ia or jb) and v ) continue ;
if ( !(ia or jb or v) ) continue ;
mini(f[t + 1][u or ja][v], f[t][i][j] + dp[cyc[t + 1]][u][v]);
}
} else if (t == m - 2) {
for(int check=1;check>0;--check) {
if ( (ja or ib) and j ) continue ;
if ( !(ja or ib or j) ) continue ;
if ( !(i or jb) ) continue ;
mini(f[t + 1][1][jb], f[t][i][j] + dp[cyc[t + 1]][ib][jb]);
}
} else {
FOR(u, 0, 1) FOR(v, 0, 1) {
if ( i and v ) continue ;
if ( !(i or v) ) continue ;
mini(f[t + 1][u or j][v], f[t][i][j] + dp[cyc[t + 1]][u][v]);
}
}
f[t][i][j] = -1;
}
if (f[m - 1][1][jb] != -1) {
ans = min(ans, f[m - 1][1][jb]);
}
FOR(i, 0, 1) FOR(j, 0, 1) f[m - 1][i][j] = -1;
}
if (ans > n) ans = -1;
cout << ans;
}
/* Let the river flows naturally */
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
