#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 2e5,mod = 1e9+7;
vector<int>adj[N];
int head[N],par[N];
int root,special;
ll dp[N][2][2][2][2];
int st(int x)
{
if (x == head[x]) return x;
return head[x] = nadi(head[x]);
}
void dfs(int x,int pr)
{
par[x] = pr;
for(auto u:adj[x])
{
if(u == pr)continue;
dfs(u,x);
}
}
ll calc(int nd,int me,int up,int rt,int sp)
{
if(dp[nd][me][up][rt][sp]!=-1)
return dp[nd][me][up][rt][sp];
bool tr = 1;
if(nd==special&&rt&&up)tr = 0;
if(nd==root&&me!=rt)tr = 0;
if(nd==special&&me!=sp)tr = 0;
if(!tr)
return dp[nd][me][up][rt][sp] = 1e18;
ll sum = me;
for(auto u:adj[nd])
{
if(u==par[nd])continue;
sum+=calc(u,0,me,rt,sp);
}
bool cmp = 0;
if(up)cmp = 1;
if(nd==root&&sp)cmp = 1;
if(nd==special&&rt)cmp = 1;
ll res = 1e18;
if(cmp)
{
res = min(res,sum);
}
else
{
for(auto u:adj[nd])
{
if(u==par[nd])continue;
ll val = sum-calc(u,0,me,rt,sp)+calc(u,1,me,rt,sp);
res = min(res,val);;
}
}
return dp[nd][me][up][rt][sp] = res;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i = 0;i<=n;i++)
head[i] = i;
for(int i = 0;i<n;i++)
{
int a,b;
cin>>a>>b;
int pa = st(a);
int pb = st(b);
if(pa==pb)
{
root = a;
special = b;
}
else
{
head[pa] = pb;
adj[a].pb(b);
adj[b].pb(a);
}
}
dfs(root,0);
ll ans = 1e18;
// cout<<root<<' '<<special<<endl;
memset(dp,-1,sizeof dp);
for(int rt = 0;rt<=1;rt++)
{
for(int sp = 0;sp<=1;sp++)
{
// cout<<calc(root,rt,0,rt,sp)<<' '<<endl;
// cout<<rt<<' '<<sp<<endl;
ans = min(ans,calc(root,rt,0,rt,sp));
}
}
if(ans==1e18)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
/*
*/
Compilation message
Main.cpp: In function 'int st(int)':
Main.cpp:22:22: error: 'nadi' was not declared in this scope
22 | return head[x] = nadi(head[x]);
| ^~~~
