#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
const int mod = 1e9 + 7;
using namespace std;
const int N = 1e5+5;
const int inf = 1e15;
vi adj[N];
vi childs[N];
vb vis(N, 0);
int dp1[N][2][2];
int dp2[N][2][2];
int dp3[N][2][2];
int dp4[N][2][2];
int x = -1, y;
set<int> setX, setY;
void cycle_dfs(int node, int par) {
vis[node] = 1;
for(int ch : adj[node]) if(ch != par) {
if(vis[ch]) {
if(x == -1) {
x = node;
y = ch;
}
} else {
cycle_dfs(ch, node);
}
}
}
void dp1_dfs(int node, int par) { // x = unc, y = unc
int chc = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
chc++;
dp1_dfs(ch, node);
}
if(chc == 0) {
dp1[node][0][0] = 0;
dp1[node][0][1] = 1;
dp1[node][1][0] = inf;
dp1[node][1][1] = inf;
if(node == x || node == y) dp1[node][0][1] = dp1[node][1][1] = inf;
return;
}
int sum1 = 0;
int sum2 = 0;
int min3 = inf;
int min4 = inf;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp1[ch][1][0];
sum2 += dp1[ch][0][0];
min3 = min(min3, dp1[ch][1][1] - dp1[ch][1][0]);
min4 = min(min4, dp1[ch][0][1] - dp1[ch][0][0]);
}
// to be uncolor and undone, all ch must be uncolor and done
// to be color and undone, all ch must be uncolor and undone
dp1[node][0][0] = min(inf, sum1);
dp1[node][0][1] = min(inf, sum2 + 1);
dp1[node][1][0] = min(inf, sum1 + min3);
dp1[node][1][1] = min(inf, sum2 + min4 + 1);
if(node == x || node == y) dp1[node][0][1] = dp1[node][1][1] = inf;
}
void dp2_dfs(int node, int par) { // x = unc, y = c
int chc = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
chc++;
dp2_dfs(ch, node);
}
if(node == x) {
dp2[node][0][0] = inf;
dp2[node][0][1] = inf;
dp2[node][1][1] = inf;
if(chc == 0) {
dp2[node][1][0] = 0;
return;
}
int sum1 = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp2[ch][1][0];
}
dp2[node][1][0] = min(inf, sum1);
return;
}
if(chc == 0) {
dp2[node][0][0] = 0;
dp2[node][0][1] = 1;
dp2[node][1][0] = inf;
dp2[node][1][1] = inf;
if(node == y) dp2[node][0][0] = dp2[node][1][0] = inf;
return;
}
int sum1 = 0;
int sum2 = 0;
int min3 = inf;
int min4 = inf;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp2[ch][1][0];
sum2 += dp2[ch][0][0];
min3 = min(min3, dp2[ch][1][1] - dp2[ch][1][0]);
min4 = min(min4, dp2[ch][0][1] - dp2[ch][0][0]);
}
dp2[node][0][0] = min(inf, sum1);
dp2[node][0][1] = min(inf, sum2 + 1);
dp2[node][1][0] = min(inf, sum1 + min3);
dp2[node][1][1] = min(inf, sum2 + min4 + 1);
if(node == y) dp2[node][0][0] = dp2[node][1][0] = inf;
}
void dp3_dfs(int node, int par) { // x = c, y = unc
int chc = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
chc++;
dp3_dfs(ch, node);
}
if(node == y) {
dp3[node][0][0] = inf;
dp3[node][0][1] = inf;
dp3[node][1][1] = inf;
if(chc == 0) {
dp3[node][1][0] = 0;
return;
}
int sum1 = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp3[ch][1][0];
}
dp3[node][1][0] = min(inf, sum1);
return;
}
if(chc == 0) {
dp3[node][0][0] = 0;
dp3[node][0][1] = 1;
dp3[node][1][0] = inf;
dp3[node][1][1] = inf;
if(node == x) dp3[node][0][0] = dp3[node][1][0] = inf;
return;
}
int sum1 = 0;
int sum2 = 0;
int min3 = inf;
int min4 = inf;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp3[ch][1][0];
sum2 += dp3[ch][0][0];
min3 = min(min3, dp3[ch][1][1] - dp3[ch][1][0]);
min4 = min(min4, dp3[ch][0][1] - dp3[ch][0][0]);
}
dp3[node][0][0] = min(inf, sum1);
dp3[node][0][1] = min(inf, sum2 + 1);
dp3[node][1][0] = min(inf, sum1 + min3);
dp3[node][1][1] = min(inf, sum2 + min4 + 1);
if(node == x) dp3[node][0][0] = dp3[node][1][0] = inf;
}
void dp4_dfs(int node, int par) { // x = c, y = unc
int chc = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
chc++;
dp4_dfs(ch, node);
}
if(node == x || node == y) {
dp4[node][0][0] = inf;
dp4[node][0][1] = inf;
dp4[node][1][0] = inf;
if(chc == 0) {
dp4[node][1][1] = 1;
return;
}
int sum1 = 0;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp4[ch][0][0];
}
dp4[node][1][1] = min(inf, sum1 + 1);
return;
}
if(chc == 0) {
dp4[node][0][0] = 0;
dp4[node][0][1] = 1;
dp4[node][1][0] = inf;
dp4[node][1][1] = inf;
if(node == x) dp4[node][0][0] = dp4[node][1][0] = inf;
return;
}
int sum1 = 0;
int sum2 = 0;
int min3 = inf;
int min4 = inf;
for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
sum1 += dp4[ch][1][0];
sum2 += dp4[ch][0][0];
min3 = min(min3, dp4[ch][1][1] - dp4[ch][1][0]);
min4 = min(min4, dp4[ch][0][1] - dp4[ch][0][0]);
}
dp4[node][0][0] = min(inf, sum1);
dp4[node][0][1] = min(inf, sum2 + 1);
dp4[node][1][0] = min(inf, sum1 + min3);
dp4[node][1][1] = min(inf, sum2 + min4 + 1);
}
void solve() {
int n;
cin >> n;
F(i, 0, n) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].pb(v);
adj[v].pb(u);
}
cycle_dfs(0, 0);
dp1_dfs(0, 0);
dp2_dfs(0, 0);
dp3_dfs(0, 0);
dp4_dfs(0, 0);
vi ans = {
dp1[0][1][0], dp1[0][1][1],
dp2[0][1][0], dp2[0][1][1],
dp3[0][1][0], dp3[0][1][1],
dp4[0][1][0], dp4[0][1][1]
};
int real_real_ans = *min_element(ans.begin(), ans.end());
int real_real_final_ans = real_real_ans >= inf ? -1 : real_real_ans;
//F(i, 0, 8) cout << ans[i] << " \n"[i == 7];
cout << real_real_final_ans << endl;
}
int32_t main() {
cin.tie(0); ios_base::sync_with_stdio(0);
#ifdef Local
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while(t--) solve();
}
# | 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... |