#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
  clock_t start;
  Timer(){
    start=clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(16);
  }
  inline double now(){return (double)(clock()-start)/1000;}
  #ifdef LOCAL
  ~Timer(){
    cerr<<"time:";
    cerr<<now();
    cerr<<"ms\n";
  }
  #endif
}timer;
void SOLVE();
int main(){
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
}
#include<type_traits>
struct has_update_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.update(),std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_update:public decltype(has_update_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_update_v=has_update<T>::value;
struct has_push_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.push(),std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_push:public decltype(has_push_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_push_v=has_push<T>::value;
struct has_middle_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.middle,std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_middle:public decltype(has_middle_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_middle_v=has_middle<T>::value;

template<typename T,bool no_push=false>
void splay(T*nd){
  if constexpr(has_push_v<T>&&!no_push)nd->push();
  while(nd->par){
    T *p=nd->par;
    T *pp=p->par;
    if constexpr(has_push_v<T>&&!no_push){
      if(pp)pp->push();
      p->push();
      nd->push();
    }
    if(p->left==nd){
      if(pp){
        if(pp->left==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          pp->left=p->right;
          if(pp->left)pp->left->par=pp;
          p->left=nd->right;
          if(p->left)p->left->par=p;
          nd->right=p;
          p->par=nd;
          p->right=pp;
          pp->par=p;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
        else if(pp->right==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          p->left=nd->right;
          if(p->left)p->left->par=p;
          pp->right=nd->left;
          if(pp->right)pp->right->par=pp;
          nd->left=pp;
          pp->par=nd;
          nd->right=p;
          p->par=nd;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
      }
      nd->par=pp;
      if(pp){
        if constexpr(has_middle_v<T>){
          if(pp->middle==p)pp->middle=nd;
          else if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
        else{
          if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
      }
      p->left=nd->right;
      if(p->left)p->left->par=p;
      nd->right=p;
      p->par=nd;
      if constexpr(has_update_v<T>)p->update(),nd->update();
      break;
    }
    else if(p->right==nd){
      if(pp){
        if(pp->left==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          p->right=nd->left;
          if(p->right)p->right->par=p;
          pp->left=nd->right;
          if(pp->left)pp->left->par=pp;
          nd->left=p;
          p->par=nd;
          nd->right=pp;
          pp->par=nd;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
        else if(pp->right==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          pp->right=p->left;
          if(pp->right)pp->right->par=pp;
          p->right=nd->left;
          if(p->right)p->right->par=p;
          nd->left=p;
          p->par=nd;
          p->left=pp;
          pp->par=p;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
      }
      nd->par=pp;
      if(pp){
        if constexpr(has_middle_v<T>){
          if(pp->middle==p)pp->middle=nd;
          else if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
        else{
          if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
      }
      p->right=nd->left;
      if(p->right)p->right->par=p;
      nd->left=p;
      p->par=nd;
      if constexpr(has_update_v<T>)p->update(),nd->update();
      break;
    }
    else break;
  }
}
template<typename T>
[[nodiscard]]T* near(T *nd,decltype(T::key)k){
  while(true){
    if(k<nd->key){
      if constexpr(has_push_v<T>)nd->push();
      if(nd->left)nd=nd->left;
      else{
        splay<T,true>(nd);
        return nd;
      }
    }
    else if(nd->key<k){
      if constexpr(has_push_v<T>)nd->push();
      if(nd->right)nd=nd->right;
      else{
        splay<T,true>(nd);
        return nd;
      }
    }
    else{
      splay<T,true>(nd);
      return nd;
    }
  }
  return nullptr;
}
template<typename T>
[[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){
  while(true){
    if constexpr(has_push_v<T>)nd->push();
    decltype(T::sz) lsz=nd->left?nd->left->sz:0;
    if(lsz==k)break;
    else if(k<lsz)nd=nd->left;
    else{
      nd=nd->right;
      k-=1+lsz;
    }
  }
  splay<T,true>(nd);
  return nd;
}
template<typename T>
[[nodiscard]]T* merge(T* l,T *r){
  if(!l)return r;
  if(!r)return l;
  while(r->left){
    if constexpr(has_push_v<T>)r->push();
    r=r->left;
  }
  if constexpr(has_push_v<T>)r->push();
  splay<T,true>(r);
  r->left=l;
  l->par=r;
  if constexpr(has_update_v<T>)r->update();
  return r;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* left_most(T*nd){
  T nil;
  T *rnd=&nil;
  while(nd->left){
    if constexpr(has_push_v<T>)nd->push();
    T *c=nd->left;
    if(!c->left){
      rnd->left=nd;
      if constexpr(has_update_v<T>||correct_parent)nd->par=rnd;
      rnd=rnd->left;
      nd=c;
    }
    else{
      if constexpr(has_push_v<T>)c->push();
      nd->left=c->right;
      c->right=nd;
      if constexpr(has_update_v<T>||correct_parent){
        if(nd->left)nd->left->par=nd;
        nd->par=c;
      }
      if constexpr(has_update_v<T>)nd->update();
      if constexpr(has_update_v<T>||correct_parent)c->par=rnd;
      rnd->left=c;
      nd=c->left;
      rnd=rnd->left;
    }
  }
  if constexpr(has_push_v<T>)nd->push();
  rnd->left=nd->right;
  nd->right=nil.left;
  nil.left=nil.right=nullptr;
  if constexpr(has_update_v<T>||correct_parent){
    if(rnd->left)rnd->left->par=rnd;
    if(nd->right)nd->right->par=nd;
    nd->par=nullptr;
  }
  if constexpr(has_update_v<T>){
    if(rnd!=&nil){
      while(rnd){
        rnd->update();
        rnd=rnd->par;
      }
    }
  }
  return nd;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* right_most(T*nd){
  T nil;
  T *lnd=&nil;
  while(nd->right){
    if constexpr(has_push_v<T>)nd->push();
    T *c=nd->right;
    if(!c->right){
      lnd->right=nd;
      if constexpr(has_update_v<T>||correct_parent)nd->par=lnd;
      lnd=lnd->right;
      nd=c;
    }
    else{
      if constexpr(has_push_v<T>)c->push();
      nd->right=c->left;
      c->left=nd;
      if constexpr(has_update_v<T>||correct_parent){
        if(nd->right)nd->right->par=nd;
        nd->par=c;
      }
      if constexpr(has_update_v<T>){
        nd->update();
      }
      if constexpr(has_update_v<T>||correct_parent)c->par=lnd;
      lnd->right=c;
      nd=c->right;
      lnd=lnd->right;
    }
  }
  if constexpr(has_push_v<T>)nd->push();
  lnd->right=nd->left;
  nd->left=nil.right;
  nil.left=nil.right=nullptr;
  if constexpr(has_update_v<T>||correct_parent){
    if(lnd->right)lnd->right->par=lnd;
    if(nd->left)nd->left->par=nd;
    nd->par=nullptr;
  }
  if constexpr(has_update_v<T>){
    if(lnd!=&nil){
      while(lnd){
        lnd->update();
        lnd=lnd->par;
      }
    }
  }
  return nd;
}
template<typename T>
void tt_expose(T*nd){
  while(true){
    splay(nd);
    if(nd->right){
      nd->right->par=nullptr;
      T *light=new T();
      light->vertex=false;
      light->middle=nd->right;
      if(nd->middle){
        light->left=nd->middle;
        light->left->par=light;
      }
      nd->middle=light;
      light->par=nd;
      nd->right->par=light;
      nd->right=nullptr;
      if constexpr(has_update_v<T>)light->update(),nd->update();
    }
    if(!nd->par)break;
    T *pon=nd->par;
    splay(pon);
    splay(pon->par);
    if constexpr(has_push_v<T>)pon->push();
    if(pon->par->right){
      pon->middle=pon->par->right;
      pon->middle->par=pon;
      pon->par->right=nd;
      nd->par=pon->par;
      if constexpr(has_update_v<T>)pon->update(),pon->par->update();
    }
    else{
      pon->par->right=nd;
      nd->par=pon->par;
      T *l=pon->left,*r=pon->right;
      if(l&&r){
        l->par=nullptr;
        r->par=nullptr;
        l=merge(l,r);
        l->par=pon->par;
        l->par->middle=l;
      }
      else if(!l&&!r){
        pon->par->middle=nullptr;
      }
      else{
        if(!l)std::swap(l,r);
        l->par=pon->par;
        l->par->middle=l;
      }
      if constexpr(has_update_v<T>)nd->par->update();
      delete(pon);
    }
  }
}
template<typename T>
void tt_link(T*u,T*v){
  tt_expose(u);
  tt_expose(v);
  v->reverse();
  u->right=v;
  v->par=u;
  if constexpr(has_update_v<T>)u->update();
}
template<typename T>
void tt_cut(T*u,T*v){
  tt_expose(u);
  u->reverse();
  tt_expose(v);
  v->left=nullptr;
  u->par=nullptr;
  if constexpr(has_update_v<T>)v->update();
}
template<typename T>
struct csr_array{
private:
  std::vector<int>ptr;
  std::vector<T>dat;
public:
  using iterator=typename std::vector<T>::iterator;
  using const_iterator=typename std::vector<T>::const_iterator;
  struct csr{
    iterator l,r;
    iterator begin(){return l;}
    iterator end(){return r;}
    int size()const{return r-l;}
    T &operator[](int i)const{return l[i];}
  };
  struct const_csr{
    const_iterator l,r;
    const_iterator begin(){return l;}
    const_iterator end(){return r;}
    int size()const{return r-l;}
    const T &operator[](int i)const{return l[i];}
  };
  csr_array():ptr{0}{}
  csr_array(int n,const std::vector<std::pair<int,T>>&a):ptr(n+1),dat(a.size()){
    for(const auto&[k,v]:a)ptr[k]++;
    for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1];
    for(int i=std::ssize(a);i--;)dat[--ptr[a[i].first]]=a[i].second;
  }
  explicit csr_array(int n,const std::vector<int>&a):ptr(n+1),dat(a.size()){
    static_assert(std::is_same_v<T,int>);
    for(const int&x:a)ptr[x]++;
    for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1];
    for(int i=std::ssize(a);i--;)dat[--ptr[a[i]]]=i;
  }
  csr operator[](int i){return csr{dat.begin()+ptr[i],dat.begin()+ptr[i+1]};}
  const_csr operator[](int i)const{return const_csr{dat.begin()+ptr[i],dat.begin()+ptr[i+1]};}
  iterator begin(){return dat.begin();}
  iterator end(){return dat.end();}
  const_iterator begin()const{return dat.begin();}
  const_iterator end()const{return dat.end();}
  int size()const{return std::ssize(ptr)-1;}
};
template<typename T=int>
struct Edge{
  int from,to;
  T weight;
  int index;
  Edge(int from_,int to_,T weight_=T(),int index_=-1):from(from_),to(to_),weight(weight_),index(index_){}
  Edge():from(-1),to(-1),weight(),index(-1){}
  friend std::ostream &operator<<(std::ostream &os,const Edge&e){
    os<<'[';
    os<<"from:"<<e.from;
    os<<"to:"<<e.to;
    os<<"weight:"<<e.weight;
    os<<"index:"<<e.index;
    os<<']';
    return os;
  }
};
template<typename T=int>
struct Tree{
  int n,r;
  std::vector<Edge<T>>edge;
  std::vector<Edge<T>>g;
  std::vector<int>ptr;
  struct tree_range{
    using iterator=typename std::vector<Edge<T>>::iterator;
    iterator l,r;
    iterator begin()const{return l;}
    iterator end()const{return r;}
    int size()const{return r-l;}
    bool empty()const{return !size();}
    Edge<T> &operator[](int i)const{return l[i];}
  };
  struct const_tree_range{
    using iterator=typename std::vector<Edge<T>>::const_iterator;
    iterator l,r;
    iterator begin()const{return l;}
    iterator end()const{return r;}
    int size()const{return r-l;}
    bool empty()const{return !size();}
    const Edge<T> &operator[](int i)const{return l[i];}
  };
  explicit Tree(int n_):n(n_){
    edge.reserve(n-1);
  }
  Tree():n(0){}
  Tree(int n_,const std::vector<Edge<T>>&e,bool dir=false):n(n_),r(-1),edge(e){
    if(!dir)build();
    else{
      std::vector<bool>seen(n,false);
      ptr.resize(n+1);
      for(const Edge<T>&i:edge)ptr[i.from]++,ptr[i.to]++,seen[e.to]=true;
      for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1];
      r=std::find(seen.begin(),seen.end(),false)-seen.begin();
      assert(ptr[n]==n*2-2);
      g.resize(ptr[n]);
      for(const Edge<T>&i:edge)g[--ptr[i.to]]=Edge<T>(i.to,i.from,i.weight,i.index);
      for(const Edge<T>&i:edge)g[--ptr[i.from]]=i;
    }
  }
  template<bool weighted=false,bool index=1>
  void read(){
    for(int i=0;i<n-1;i++){
      int u,v;
      T w=T();
      std::cin>>u>>v;
      if constexpr(index)u--,v--;
      if constexpr(weighted)std::cin>>w;
      else w=1;
      edge.emplace_back(u,v,w,i);
    }
    build();
  }
  template<bool index=1>
  void readp(){
    ptr.resize(n+1);
    for(int i=1;i<n;i++){
      int p;
      std::cin>>p;
      if constexpr(index)p--;
      edge.emplace_back(p,i,1,i-1);
      ptr[p]++;
      ptr[i]++;
    }
    for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1];
    g.resize(n*2-2);
    for(auto&&[u,v,w,i]:edge)g[--ptr[v]]=Edge<T>(v,u,w,i);
    for(int i=0;i<n-1;i++){
      g[--ptr[edge[i].from]]=edge[i];
    }
    r=0;
  }
  void add_edge(int u,int v){edge.emplace_back(u,v,1,edge.size());}
  void add_edge(int u,int v,T w){edge.emplace_back(u,v,w,edge.size());}
  void add_edge(int u,int v,T w,int idx){edge.emplace_back(u,v,w,idx);}
  inline bool is_directed()const{return r!=-1;}
  void build(){
    r=-1;
    ptr.resize(n+1,0);
    for(auto&&[u,v,w,i]:edge)ptr[u]++,ptr[v]++;
    for(int i=1;i<=n;i++)ptr[i]+=ptr[i-1];
    assert(ptr[n]==n*2-2);
    g.resize(n*2-2);
    for(auto&&[u,v,w,i]:edge){
      g[--ptr[u]]=Edge(u,v,w,i);
      g[--ptr[v]]=Edge(v,u,w,i);
    }
  }
  void remove_parent(int root=0){
    edge.resize(n-1);
    std::vector<int>par(n,-1);
    par[root]=-1;
    std::queue<int>que;
    que.push(root);
    while(!que.empty()){
      int x=que.front();
      que.pop();
      for(int i=ptr[x];i<ptr[x+1];){
        const Edge<T>&e=g[i];
        if(e.to!=par[x]){
          par[e.to]=x;
          assert(e.index<n-1);
          edge[e.index]=e;
          que.push(e.to);
          i++;
        }
        else{
          if(i+1==ptr[x+1])break;
          std::swap(g[i],g[ptr[x+1]-1]);
        }
      }
    }
    r=root;
  }
  std::vector<int>bfs_order()const{
    assert(is_directed());
    std::vector<int>bfs(n);
    int p=0,q=0;
    bfs[q++]=root();
    while(p<q){
      int x=bfs[p++];
      for(const Edge<T>&e:(*this)[x])bfs[q++]=e.to;
    }
    return bfs;
  }
  std::vector<int>dfs_order()const{
    assert(is_directed());
    std::vector<int>res;
    res.reserve(n);
    std::vector<int>st(n);
    int p=0;
    st[p++]=root();
    while(p){
      int x=st[--p];
      res.push_back(x);
      p+=(*this)[x].size();
      for(const Edge<T>&e:(*this)[x])st[--p]=e.to;
      p+=(*this)[x].size();
    }
    return res;
  }
  std::vector<int>rbfs_order()const{
    std::vector<int>bfs=bfs_order();
    std::reverse(bfs.begin(),bfs.end());
    return bfs;
  }
  void hld(){
    assert(is_directed());
    std::vector<int>sub(n);
    for(int x:rbfs_order()){
      sub[x]=1;
      int mx=-1;
      for(Edge<T>&e:(*this)[x]){
        sub[x]+=sub[e.to];
        if(mx<sub[e.to]){
          mx=sub[e.to];
          std::swap((*this)[x][0],e);
        }
      }
    }
  }
  std::pair<std::vector<int>,std::vector<int>>in_out_order(){
    assert(is_directed());
    std::vector<int>in(n),out(n);
    int p=0;
    auto dfs=[&](auto self,int x)->void {
      in[x]=p++;
      for(const Edge<T>&e:(*this)[x]){
        self(self,e.to);
      }
      out[x]=p;
    };
    dfs(dfs,root());
    return std::make_pair(in,out);
  }
  std::pair<T,std::vector<int>>diameter()const{
    assert(!is_directed());
    static constexpr T inf=std::numeric_limits<T>::max();
    std::vector<T>dst(n,inf);
    dst[0]=0;
    std::vector<int>que(n);
    int p=0,q=1;
    que[0]=0;
    while(p<q){
      int x=que[p++];
      for(const Edge<T>&e:(*this)[x])if(dst[e.to]==inf){
        dst[e.to]=dst[x]+e.weight;
        que[q++]=e.to;
      }
    }
    int u=std::max_element(dst.begin(),dst.end())-dst.begin();
    std::fill(dst.begin(),dst.end(),inf);
    dst[u]=0;
    p=0,q=1;
    que[0]=u;
    while(p<q){
      int x=que[p++];
      for(const Edge<T>&e:(*this)[x])if(dst[e.to]==inf){
        dst[e.to]=dst[x]+e.weight;
        que[q++]=e.to;
      }
    }
    int v=std::max_element(dst.begin(),dst.end())-dst.begin();
    T weight=dst[v];
    std::vector<int>res;
    while(u!=v){
      res.push_back(v);
      for(const Edge<T>&e:(*this)[v])if(dst[e.to]<dst[v]){
        v=e.to;
        break;
      }
    }
    res.push_back(u);
    return std::make_pair(weight,res);
  }
  int size()const{return n;}
  tree_range operator[](int i){return tree_range{g.begin()+ptr[i],g.begin()+ptr[i+1]-(r!=-1&&r!=i)};}
  const_tree_range operator[](int i)const{return const_tree_range{g.begin()+ptr[i],g.begin()+ptr[i+1]-(r!=-1&&r!=i)};}
  const Edge<T>& get_edge(int i)const{return edge[i];}
  inline int parent(int i)const{return i==r?-1:g[ptr[i+1]-1].to;}
  inline int root()const{return r;}
  typename std::vector<Edge<T>>::iterator begin(){return edge.begin();}
  typename std::vector<Edge<T>>::iterator end(){return edge.end();}
  typename std::vector<Edge<T>>::const_iterator begin()const{return edge.begin();}
  typename std::vector<Edge<T>>::const_iterator end()const{return edge.end();}
};
struct LevelAncestor{
  csr_array<int>bin;
  std::vector<int>pos,dep,dfs;
  LevelAncestor(){}
  template<typename T>
  LevelAncestor(Tree<T> t){
    int n=t.size();
    pos.resize(n),dep.resize(n);
    std::vector<int>bin_v;
    bin_v.reserve(n);
    dfs=t.dfs_order();
    for(int x:dfs){
      pos[x]=bin_v.size();
      bin_v.push_back(dep[x]);
      for(const Edge<T>&e:t[x])dep[e.to]=dep[x]+1;
    }
    bin=csr_array<int>(*std::max_element(bin_v.begin(),bin_v.end())+1,bin_v);
  }
  int query(int u,int d)const{
    if(dep[u]<d)return -1;
    return dfs[*std::prev(std::upper_bound(bin[dep[u]-d].begin(),bin[dep[u]-d].end(),pos[u]))];
  }
};
#include<concepts>
template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);}

template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);}

template<std::integral T>
constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);}
template<std::integral T>
constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);}
template<typename M,int L=5>
struct SparseTable{
  using S=typename M::S;
private:
  std::vector<S>dat,prefix,suffix;
  std::vector<std::vector<S>>sp;
public:
  SparseTable(){}
  SparseTable(std::vector<S>a):dat(a){
    int n=a.size();
    n=(n+(1<<L)-1)&~((1<<L)-1);
    a.resize(n,M::e());
    prefix=suffix=a;
    std::vector<S>d2(n>>L,M::e());
    for(int i=0;i<(int)d2.size();i++){
      for(int j=0;j<(1<<L);j++)d2[i]=M::op(d2[i],a[(i<<L)+j]);
    }
    for(int i=0;i<(n>>L);i++){
      for(int j=1;j<(1<<L);j++)prefix[(i<<L)+j]=M::op(prefix[(i<<L)+j-1],prefix[(i<<L)+j]);
    }
    for(int i=(n>>L)-1;i>=0;i--){
      for(int j=(1<<L)-1;j>=1;j--)suffix[(i<<L)+j-1]=M::op(suffix[(i<<L)+j-1],suffix[(i<<L)+j]);
    }
    int d=(d2.size()==1?1:32-__builtin_clz(d2.size()-1));
    sp.resize(d,d2);
    for(int i=1;i<d;i++){
      int w=1<<i;
      for(int j=w;j<=(int)d2.size();j+=w*2){
        for(int k=j-2;k>=j-w;k--)sp[i][k]=M::op(d2[k],sp[i][k+1]);
        int r=std::min<int>(d2.size(),j+w);
        for(int k=j+1;k<r;k++)sp[i][k]=M::op(sp[i][k-1],d2[k]);
      }
    }
  }
  S prod(int l,int r)const{
    if(l==r)return M::e();
    r--;
    int lid=l>>L,rid=r>>L;
    if(lid==rid){
      S ret=M::e();
      for(int i=l;i<=r;i++)ret=M::op(ret,dat[i]);
      return ret;
    }
    else{
      lid++;
      rid--;
      S mid=M::e();
      if(lid==rid)mid=sp[0][lid];
      else if(lid<rid){
        int s=msb(lid^rid);
        mid=M::op(sp[s][lid],sp[s][rid]);
      }
      return M::op(suffix[l],M::op(mid,prefix[r]));
    }
  }
};
struct LowestCommonAncestor{
private:
  struct p_min{
    using S=std::pair<int,int>;
    static S op(const S&x,const S&y){return x.first<y.first?x:y;}
    static S e(){return std::make_pair(std::numeric_limits<int>::max(),-1);}
  };
  SparseTable<p_min>sp;
  std::vector<int>idx;
public:
  template<typename T>
  LowestCommonAncestor(const Tree<T>&t):idx(t.size()){
    assert(t.is_directed());
    int r=t.root();
    int ord=0;
    std::vector<int>dep(t.size());
    dep[r]=0;
    std::vector<std::pair<int,int>>init(t.size()*2-1);
    auto dfs=[&](auto&&self,int x)->void {
      idx[x]=ord;
      init[ord++]=std::make_pair(dep[x],x);
      for(const auto&e:t[x]){
        dep[e.to]=dep[e.from]+1;
        self(self,e.to);
        init[ord++]=std::make_pair(dep[x],x);
      }
    };
    dfs(dfs,r);
    sp=SparseTable<p_min>(init);
  }
  LowestCommonAncestor(){}
  int query(int u,int v)const{
    if(u==v)return u;
    if(idx[u]>idx[v])std::swap(u,v);
    return sp.prod(idx[u],idx[v]+1).second;
  }
};
struct JumponTree{
private:
  LowestCommonAncestor lca;
  LevelAncestor la;
public:
  template<typename T>
  JumponTree(Tree<T>t){
    t.remove_parent();
    lca=LowestCommonAncestor(t);
    la=LevelAncestor(std::move(t));
  }
  int jump(int u,int v,int d)const{
    int l=lca.query(u,v);
    if(la.dep[u]+la.dep[v]-la.dep[l]*2<d)return -1;
    if(la.dep[u]-la.dep[l]>=d)return la.query(u,d);
    else return la.query(v,la.dep[u]+la.dep[v]-la.dep[l]*2-d);
  }
};
struct Path{
  int lb=1e9,rb=1e9;
  bool contain_b=false;
  int len=0;
  int ans=0;
  int e=0;
  friend ostream &operator<<(ostream&os,const Path&p){
    os<<p.lb<<' '<<p.rb<<' '<<p.contain_b<<' '<<p.len<<' '<<p.ans<<' '<<p.e;
    return os;
  }
};
struct Point{
  int b=1e9;
  int b_cnt=0;
  int ans=0;
  friend ostream &operator<<(ostream&os,const Point&p){
    os<<p.b<<' '<<p.b_cnt<<' '<<p.ans;
    return os;
  }
};
Path compress(Path l,Path r){
  Path res;
  // res.lb=min(l.lb,l.len+r.lb);
  // res.rb=min(l.rb+r.len,r.rb);
  res.len=l.len+r.len;
  res.contain_b=l.contain_b||r.contain_b;
  if(l.contain_b&&r.contain_b){
    res.ans=l.ans+r.ans+l.rb+r.lb+l.e+r.e;
    res.e=0;
    res.lb=l.lb;
    res.rb=r.rb;
  }
  else if(l.contain_b){
    res.ans=l.ans;
    res.e=l.e;
    res.lb=l.lb;
    res.rb=l.rb+r.len;
  }
  else if(r.contain_b){
    res.ans=r.ans;
    res.e=r.e;
    res.lb=r.lb+l.len;
    res.rb=r.rb;
  }
  else{
    res.ans=0;
    res.e=0;
    res.lb=res.rb=0;
  }
  return res;
}
Point rake(Point l,Point r){
  Point res;
  res.b=min(l.b,r.b);
  res.b_cnt=l.b_cnt+r.b_cnt;
  res.ans=l.ans+r.ans;
  if(l.b_cnt&&r.b_cnt){
    if(l.b_cnt==1)res.ans+=l.b;
    if(r.b_cnt==1)res.ans+=r.b;
  }
  return res;
}
Path add_vertex(Point p,bool b){
  Path res;
  // res.lb=res.rb=p.b+1;
  res.len=1;
  res.contain_b=b||p.b_cnt!=0;
  res.ans=p.ans;
  if(b||p.b_cnt>=2){
    res.ans++;
    if(b&&p.b_cnt==1){
      res.ans+=p.b;
    }
    res.lb=res.rb=0;
    res.e=0;
  }
  else{
    res.lb=res.rb=1;
    res.e=p.b;
  }
  // else if(p.b_cnt>=2)res.ans++;
  return res;
}
Point add_edge(Path p){
  Point res;
  res.b=p.lb+p.e;
  res.b_cnt=p.contain_b;
  res.ans=p.ans;
  return res;
}
Path vertex2(bool b){
  if(b){
    return {0,0,true,1,1,0};
  }
  else{
    return {(int)1e9,(int)1e9,false,1,0,0};
  }
}
struct node{
  node *left=nullptr,*right=nullptr,*par=nullptr,*middle=nullptr;
  bool vertex=false;
  bool b=false;
  Path dat1,dat1rev;
  Point dat2;
  bool rev=false;
  void reverse(){
    rev^=1;
    swap(dat1,dat1rev);
    swap(left,right);
  }
  void push(){
    if(rev){
      if(left)left->reverse();
      if(right)right->reverse();
      rev=false;
    }
  }
  void update(){
    if(vertex){
      if(middle)dat1=add_vertex(middle->dat2,b);
      else dat1=vertex2(b);
      dat1rev=dat1;
      if(left)dat1=compress(left->dat1,dat1),dat1rev=compress(dat1rev,left->dat1rev);
      if(right)dat1=compress(dat1,right->dat1),dat1rev=compress(right->dat1rev,dat1rev);
    }
    else{
      assert(middle);
      dat2=add_edge(middle->dat1);
      if(left)dat2=rake(left->dat2,dat2);
      if(right)dat2=rake(dat2,right->dat2);
    }
  }
};
void SOLVE(){
  int n;
  cin>>n;
  vector<node>nds(n);
  vector<pair<int,int>>edge(n-1);
  cin>>edge;
  edge--;
  Tree t(n);
  rep(i,n){
    int c;
    cin>>c;
    // nds[i].dat1=nds[i].dat1=vertex2(c);
    nds[i].b=c;
    nds[i].vertex=true;
    nds[i].update();
  }
  for(auto [u,v]:edge){
    tt_link(&nds[u],&nds[v]);
    t.add_edge(u,v);
  }
  t.build();
  JumponTree jt(t);
  t.remove_parent();
  LowestCommonAncestor lca(t);
  vector<int>dep(n);
  for(int x:t.bfs_order()){
    for(auto e:t[x])dep[e.to]=dep[x]+1;
  }
  auto distance=[&](int u,int v)->int {
    return dep[u]+dep[v]-dep[lca.query(u,v)]*2;
  };
  int q;
  cin>>q;
  auto print=[&](){
    node*root=&nds[0];
    while(root->par)root=root->par;
    map<node*,int>mp;
    auto idx=[&](node *nd)->int {
      if(!nd)return -1;
      if(!mp.contains(nd)){
        int s=mp.size();
        mp[nd]=s;
      }
      return mp[nd];
    };
    rep(i,n)mp[&nds[i]]=i;
    set<node*>vis;
    auto dfs=[&](auto self,node *nd)->void {
      if(!nd)return;
      if(vis.contains(nd))return;
      vis.insert(nd);
      debug(idx(nd),idx(nd->left),idx(nd->right),idx(nd->par),idx(nd->middle));
      if(idx(nd)<n)debug(nd->dat1);
      else debug(nd->dat2);
      self(self,nd->left);
      self(self,nd->right);
      self(self,nd->middle);
    };
    debug("------------------------");
    dfs(dfs,root);
    debug("------------------------");
  };
  while(q--){
    int op;
    cin>>op;
    if(op==1){
      int v;
      cin>>v;
      v--;
      tt_expose(&nds[v]);
      nds[v].b^=1;
      nds[v].update();
    }
    else{
      int x,y;
      cin>>x>>y;
      x--,y--;
      if(x!=y){
        x=jt.jump(x,y,distance(x,y)-1);
        tt_cut(&nds[x],&nds[y]);
      }
      tt_expose(&nds[y]);
      cout<<nds[y].dat1.ans<<'\n';
      if(x!=y)tt_link(&nds[x],&nds[y]);
    }
  }
}