#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3HspL4A ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vec(int);
void print(){cout<<"\n";}
template<class T,class...E>
void print(const T&v,const E&...u){cout<<v<<' ',print(u...);}
// e
const int inf=1e9+11;
const int nax=100000;
int n,root,ru,usd[nax+11];
vi adj[nax+11];
void get_root(int v,int par){
if(root!=-1) return;
usd[v]=1;
for(auto u:adj[v]){
if(u==par) continue;
if(usd[u]){
root=v;
ru=u;
return;
}
get_root(u,v);
}
}
int xru,yru,dp[nax+11][2][2];
void quq(int v,int par){
dp[v][0][0]=0;
dp[v][1][0]=1;
bool pok=0;
for(auto u:adj[v]){
if(u==par) continue;
pok=pok or (u==ru);
quq(u,v);
dp[v][0][0]+=dp[u][0][1];
dp[v][1][0]+=dp[u][0][0];
}
dp[v][0][1]=dp[v][1][1]=inf;
for(auto u:adj[v]){
if(u==par) continue;
dp[v][0][1]=min(dp[v][0][1],dp[v][0][0]-dp[u][0][1]+dp[u][1][1]);
dp[v][1][1]=min(dp[v][1][1],dp[v][1][0]-dp[u][0][0]+dp[u][1][0]);
}
if(pok){
rep(t,2)rep(t1,2) dp[v][t][t1]=inf;
if(xru){
if(yru) dp[v][1][1]=1;
dp[v][0][1]=0;
for(auto u:adj[v]){
if(u==par) continue;
if(u!=ru){
if(yru) dp[v][1][1]+=dp[u][0][0];
dp[v][0][1]+=dp[u][0][1];
}else{
if(yru) dp[v][1][1]+=dp[u][1][0];
dp[v][0][1]+=dp[u][1][1];
}
}
}else{
dp[v][0][0]=0;
if(yru) dp[v][1][0]=1;
for(auto u:adj[v]){
if(u==par) continue;
if(u!=ru){
dp[v][0][0]+=dp[u][0][1];
if(yru) dp[v][1][0]+=dp[u][0][0];
}else{
dp[v][0][0]+=dp[u][0][1];
if(yru) dp[v][1][0]+=dp[u][0][0];
}
}
for(auto u:adj[v]){
if(u==par) continue;
if(u==ru) continue;
dp[v][0][1]=min(dp[v][0][1],dp[v][0][0]-dp[u][0][1]+dp[u][1][1]);
if(yru) dp[v][1][1]=min(dp[v][1][1],dp[v][1][0]-dp[u][0][0]+dp[u][1][0]);
}
}
}
}
signed main(){
_3HspL4A;
cin>>n;
rep(i,n){
int u,v;
cin>>u>>v;
u-=1,v-=1;
adj[u].pb(v);
adj[v].pb(u);
}
root=-1;
get_root(0,-1);
{
rep(i,sz(adj[root])){
if(adj[root][i]==ru){
adj[root].erase(adj[root].begin()+i);
break;
}
}
rep(i,sz(adj[ru])){
if(adj[ru][i]==root){
adj[ru].erase(adj[ru].begin()+i);
break;
}
}
}
int ans=inf;
rep(t,2){
rep(t1,2){
yru=!t1,xru=!t;
rep(i,n){
dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=inf;
}
quq(root,-1);
ans=min(ans,dp[root][t][t1]);
}
}
print(ans>=inf?-1:ans);
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
