//I love ManchesterUnited
#include<bits/stdc++.h>
using namespace std;
#define love ManchesterUnited
#define pb push_back
#define FOR(i,a,b) for (int i=(a); i<=(b); i++)
#define FORD(i,b,a) for (int i=(b); i>=(a); i--)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define endl '\n'
const int MAXN = 1005;
int n;
vector<int> adj[MAXN];
int pet[MAXN];
int dangerLevel() {
vector<int> cats, dogs;
FOR(i,1,n){
if (pet[i]==1) cats.pb(i);
if (pet[i]==2) dogs.pb(i);
}
if (cats.empty() || dogs.empty()) return 0;
int ans = 1e9;
for (int c : cats){
queue<int> q;
vector<int> dist(n+1,-1);
q.push(c); dist[c]=0;
while(!q.empty()){
int u = q.front(); q.pop();
if (pet[u]==2){
ans = min(ans, dist[u]);
break;
}
for (int v: adj[u]){
if (dist[v]==-1){
dist[v]=dist[u]+1;
q.push(v);
}
}
}
}
if (ans==1e9) return 0;
return ans;
}
void initialize(int N, vector<int> A, vector<int> B){
n = N;
FOR(i,1,n){ adj[i].clear(); pet[i]=0; }
for (int i = 0; i < N-1; i++){
int u = A[i], v = B[i];
adj[u].pb(v);
adj[v].pb(u);
}
}
int cat(int v){
pet[v] = 1;
return dangerLevel();
}
int dog(int v){
pet[v] = 2;
return dangerLevel();
}
int neighbor(int v){
pet[v] = 0;
return dangerLevel();
}
