#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll n,a[N],cntc[N],cntd[N],m;
vector<ll>g[N];
void initialize(int N, std::vector<int> A, std::vector<int> B) {
m=A.size();
n=N;
for(ll i=0;i<m;i++){
ll u=A[i];
ll v=B[i];
assert(u>0&&u<=n);
assert(v>0&&v<=n);
g[v].push_back(u);
g[u].push_back(v);
}
}
ll calc(){
ll ans=0;
for(ll i=1;i<=n;i++){
if(a[i]==0)continue;
for(auto to:g[i]){
if(a[to]==1&&a[i]==-1)ans++;
if(!a[to]){
if(a[i]==-1)cntc[to]++;
else cntd[to]++;
}
}
}
for(ll i=1;i<=n;i++){
if(a[i])continue;
ans+=min(cntc[i],cntd[i]);
cntc[i]=0;
cntd[i]=0;
}return ans;
}
int cat(int v) {
a[v]=1;
return calc();
}
int dog(int v) {
a[v]=-1;
return calc();
}
int neighbor(int v) {
ll x=a[v];
a[v]=0;
ll pos=0,ans=1e18;
for(ll to:g[v]){
if(a[to])continue;
a[to]=x;
ll cur=calc();
if(cur<ans){
ans=cur;
pos=to;
}a[to]=0;
}a[pos]=x;
return calc();
}
