断环后把断的边所连的两个点特殊标记，作为两个特殊点。这样就是一个树，树的做法很简单吧，把两个特殊点特殊处理带进状态即可。
具体一点就是，设 \(f(x,c_x,c_f,c_{rt_1},c_{rt_2})\) 表示处理到 \(x\) 点，\(x\) / \(x\) 的前驱 / 特殊点 1 / 特殊点 2 是否染色，转移很基础，具体看代码（代码中写的是状压）。
注意判无解……
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
template<typename T=int> inline T read() {
T x=0; char c=getchar(); bool f=0;
while(c<'0' || c>'9') f|=c=='-',c=getchar();
while(c>='0' && c<='9') x=x*10+(c&15),c=getchar();
return f?-x:x;
}
__attribute__((target("avx"), optimize("O3", "unroll-loops")))
const int INF=1e9+7;
int n,fa[100100],rt,exrt,dp[100100][17];
vector<int> e[100100];
int makeSta(vector<int> v) {
int res=0; assert(v.size()==4u);
for(int i=0; i<4; ++i) {
res+=(1<<(3-i))*v[i];
assert(0<=v[i] && v[i]<=1);
}
return res;
}
int GetAns(const int now,const int f,const int Sta) {
// Sta: colnow(3), colf(2), colrt(1), colexrt(0)
if(~dp[now][Sta]) return dp[now][Sta];
if((now==rt && ((Sta>>3)&1)!=((Sta>>1)&1))
|| (now==exrt && (((Sta>>3)&1)!=(Sta&1))) || (now==exrt && (Sta>>2)&1 && (Sta>>1)&1)) return dp[now][Sta]=INF;
int cnt=(Sta>>3)&1,res=INF; // number of vertexes coloured
for(const int y:e[now]) if(y!=f) cnt+=GetAns(y,now,makeSta({0,(Sta>>3)&1,(Sta>>1)&1,Sta&1}));
if((Sta>>2)&1 || (now==rt && Sta&1) || (now==exrt && (Sta>>1)&1)) cmin(res,cnt);
else {
for(const int y:e[now]) if(y!=f) cmin(res,cnt-GetAns(y,now,makeSta({0,(Sta>>3)&1,(Sta>>1)&1,Sta&1}))
+GetAns(y,now,makeSta({1,(Sta>>3)&1,(Sta>>1)&1,Sta&1})));
}
return dp[now][Sta]=res;
}
int find(int now) { while(now!=fa[now]) now=fa[now]=fa[fa[now]]; return now; }
signed main() {
// freopen("logicians.in","r",stdin);
// freopen("logicians.out","w",stdout);
memset(dp,-1,sizeof dp);
n=read();
for(int i=1; i<=n; ++i) fa[i]=i;
for(int i=1,x,y; i<=n; ++i) {
x=read(),y=read();
if(find(x)!=find(y)) {
fa[find(x)]=find(y);
e[x].push_back(y);
e[y].push_back(x);
}
else rt=x,exrt=y;
}
int ret=INF;
for(const int i:{0,1}) for(const int j:{0,1}) cmin(ret,GetAns(rt,0,makeSta({i,0,i,j})));
if(ret==INF) return puts("-1"),0;
printf("%lld\n",ret);
return 0;
}