#include <bits/stdc++.h>
#include "catdog.h"
#define fi first
#define se second
#define bit(mask, i) (((mask) >> (i)) & 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int NMAX = 1e5+5;
const int INF = 1e9+5;
int n;
vector<pii> g[NMAX];
int a[NMAX], daddy[NMAX];
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i = 0; i < n - 1; i++) {
g[A[i]].push_back({ B[i], i });
g[B[i]].push_back({ A[i], i });
}
}
bool check(int mask) {
int vis = 0;
function<bool(int, int)> dfs = [&](int x, int t) {
if (a[x] != t && a[x]) return false;
vis |= 1 << x;
for (auto &u : g[x]) {
if (!bit(mask, u.se) && !bit(vis, u.fi)) {
if (!dfs(u.fi, t))
return false;
}
}
return true;
};
for (int i = 1; i <= n; i++) {
if (a[i] && !bit(vis, i) && !dfs(i, a[i]))
return false;
}
return true;
}
int calc() {
int ret = INF;
for (int mask = 0; mask < 1 << (n - 1); mask++) {
if (__builtin_popcount(mask) >= ret)
continue;
if (check(mask))
ret = __builtin_popcount(mask);
}
return ret;
}
int cat(int v) {
a[v] = 1;
return calc();
}
int dog(int v) {
a[v] = 2;
return calc();
}
int neighbor(int v) {
a[v] = 0;
return calc();
}
