#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 1005;
vector<int> g[maxN];
int dp[maxN][2], clr[maxN];
void initialize(int n, vector<int> a, vector<int> b) {
for (int i = 0; i < n - 1; i++) {
g[a[i]].pb(b[i]); g[b[i]].pb(a[i]);
}
}
void solve(int v = 1, int p = -1) {
dp[v][0] = dp[v][1] = inf;
for (int u : g[v]) {
if (u == p) continue;
solve(u, v);
dp[v][0] = min(dp[u][0], dp[u][1] + 1);
dp[v][1] = min(dp[u][1], dp[u][0] + 1);
}
if (clr[v] == 1) dp[v][1] = inf;
if (clr[v] == 2) dp[v][0] = inf;
}
int cat(int v) {
clr[v] = 1; solve();
return min(dp[1][0], dp[1][1]);
}
int dog(int v) {
clr[v] = 2; solve();
return min(dp[1][0], dp[1][1]);
}
int neighbor(int v) {
clr[v] = 0; solve();
return min(dp[1][0], dp[1][1]);
}
