#include "catdog.h"
#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b;i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int MAXN = 2000+5;
vector<ll> adj[MAXN*3];
ll color[MAXN*3];
pair<ll,ll> ract[MAXN*3];
ll n;
ll last;
ll res = 0;
pair<ll,ll> act = {0,0};
void dfs(ll nd, ll p){
for(auto i:adj[nd]) if(i!=p){
if(color[i]==1){ act.fst++; continue; }
if(color[i]==2){ act.snd++; continue; }
dfs(i,nd);
}
}
void ndfs(ll nd, ll p){
ract[nd]=act;
for(auto i:adj[nd]) if(i!=p && color[i]==0){
ndfs(i,nd);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
last=n;
forn(i,0,n-1){
A[i]--;
B[i]--;
adj[A[i]].pb(last);
adj[last].pb(A[i]);
adj[B[i]].pb(last);
adj[last].pb(B[i]);
last++;
}
mset(color,0);
forn(i,0,MAXN*3) ract[i]={0,0};
}
int cat(int v) { v--;
color[v]=1;
res-=min(ract[v].fst,ract[v].snd);
for(auto i:adj[v]){
act={0,0};
dfs(i,-1);
res+=min(act.fst,act.snd);
ndfs(i,-1);
}
return res;
}
int dog(int v) { v--;
color[v]=2;
res-=min(ract[v].fst,ract[v].snd);
for(auto i:adj[v]){
act={0,0};
dfs(i,-1);
res+=min(act.fst,act.snd);
ndfs(i,-1);
}
return res;
}
int neighbor(int v) { v--;
color[v]=0;
for(auto i:adj[v]){
res-=min(ract[i].fst,ract[i].snd);
}
act={0,0};
dfs(v,-1);
res+=min(act.fst,act.snd);
ndfs(v,-1);
return res;
}
