#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
int x;
const int MAXN = 1000 + 15;
const int INF = 2139062143;
vector <int> adj[MAXN];
int type[MAXN];
int dp[MAXN][3];
int mn[MAXN];
void initialize(int N, std::vector<int> A, std::vector<int> B) {
x = A.size();
memset(type, 0, sizeof(type));
for (int i = 0; i < x; ++i) {
int a = A[i], b = B[i];
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
}
void DFS(int v, int p = -1) {
for (auto u : adj[v]) {
if (u != p) {
DFS(u, v);
}
}
for (int myType = 0; myType < 3; ++myType) {
if (type[v] != 0 && myType != type[v]) {continue;}
dp[v][myType] = 0;
for (auto u : adj[v]) {
if (u == p) {continue;}
//удаляю ребро
int now = mn[u] + 1;
for (int nxtType = 0; nxtType < 3; ++nxtType) {
if (dp[u][nxtType] == INF) { continue; }
// оставляю ребро
if (nxtType != 0 && myType != nxtType) { continue; }
now = min(now, dp[u][nxtType]);
}
dp[v][myType] += now;
}
}
mn[v] = min({dp[v][0], dp[v][1], dp[v][2]});
}
int Calc() {
memset(dp, 127, sizeof(dp));
memset(mn, 127, sizeof(mn));
DFS(1);
return mn[1];
}
int cat(int v) {
type[v] = 1;
return Calc();
}
int dog(int v) {
type[v] = 2;
return Calc();
}
int neighbor(int v) {
type[v] = 0;
return Calc();
}
