#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];
bool on[N];
void dfs(int u, int p) {
st.push(u);
vis[u] = 1;
on[u] = 1;
for(int v : g[u]) if (v ^ p) {
if (vis[v] == 0) {
dfs(v, u);
} else if (on[v]) {
// (u->v) canh nguoc
// cerr << u << ' ' << v << nl;
while (sz(st)){
int u = st.top();
st.pop();
on[u]=0;
cyc.push_back(u);
if (u == v) break ;
}
return ;
}
}
if (sz(st))
st.pop(), on[u]=0;
}
long long dp[N][2][2], s[2][2];
const int INF = (int)1e8;
const bool DEBUG = 0;
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);
}
if (DEBUG) {
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 & d) or (b & c) ) 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(i, 1, n) on[i]=0;
for(int x : cyc) on[x] = 1;
for(int x : cyc) {
dfs2(x, 0);
}
if (DEBUG) {cout<<"cyc: ";for(int x : cyc) 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];
// if (ia!=0 or ja!=0 or ib!=0 or jb!=0) continue;
if (DEBUG) {
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 and f[t][i][j] < INF) {
if (DEBUG) {
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 ;
if ( j and u ) 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 ;
if (i and 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 ;
if (j and u) continue ;
// cerr << t << ' ' << i << ' ' << j << ' ' << u << ' ' << v << ' ' << dp[cyc[t+1]][u][v] << nl;
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) {
if (DEBUG) {
cout << "valid - state: ";
cout << ia << ' ' << ja << ' ' << ib << ' ' << jb
<< nl;
}
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 */
